Leaders, followers, and community detection
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/91858 |
| _version_ | 1811086517476524032 |
|---|---|
| author | Parthasarathy, Dhruuv |
| author2 | Devavrat Shah. |
| author_facet | Devavrat Shah. Parthasarathy, Dhruuv |
| author_sort | Parthasarathy, Dhruuv |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. |
| first_indexed | 2024-09-23T13:27:12Z |
| format | Thesis |
| id | mit-1721.1/91858 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:27:12Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/918582019-04-11T13:52:34Z Leaders, followers, and community detection Fast, non-parametric detection of overlapping communities : the Leader-Follower algorithm Leader-Follower algorithm Parthasarathy, Dhruuv Devavrat Shah. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. Cataloged from PDF version of thesis. Includes bibliographical references (pages 53-55). Communities in social interaction networks or graphs are sets of well-connected, and very often overlapping vertices. Formally, we view any maximal clique of the social network graph as a community. The problem of finding maximal cliques is known to be computationally hard. The goal of this work is to identify structural conditions in social network graphs that lead to efficient identification of maximal cliques, i.e. overlapping communities. We propose an evolutionary model called sequential community graphs for community formation in social networks. In a sequential community graph, each node enters the graph by either joining an existing community, or creating its own. To discover communities, i.e. maximal cliques, in such graphs, we present the non-parametric Iterative Leader-Follower Algorithm (ILFA). We establish that the ILFA finds all the communities/maximal cliques correctly in the sequential community graph model in polynomial time in the number of vertices in the graph. To scale to very large data sets, we propose a minor simplification of the ILFA, called the fast leader-follower algorithm (FLFA) which effectively runs in linear time in the input data size, and finds all communities correctly for sequential community graphs with an additional constraint. Empirically, the FLFA and IFLA perform nearly the same in terms of accuracy, but the FLFA runs nearly three orders of magnitude faster. We find that the sequential community graph model is a good fit for a wide variety of social networks where users can be modeled as entering the graph by joining existing communities or creating their own. In such social networks, we demonstrate that the FLFA and ILFA outperform other state of the art algorithms both in terms of speed and accuracy. For example, in the Internet Movie Database (IMDB) graph where communities naturally correspond to actors in the same movie, our algorithms finds nearly all ground truth communities correctly while all other known community detection algorithms do very poorly. Similar empirical results are found for various other social data sets. This supports our hypothesis that we can model many social graphs as sequential community graphs and accurately detect their communities using the ILFA or FLFA. by Dhruuv Parthasarathy. M. Eng. 2014-11-24T18:40:28Z 2014-11-24T18:40:28Z 2014 2014 Thesis http://hdl.handle.net/1721.1/91858 894353059 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 55 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Parthasarathy, Dhruuv Leaders, followers, and community detection |
| title | Leaders, followers, and community detection |
| title_full | Leaders, followers, and community detection |
| title_fullStr | Leaders, followers, and community detection |
| title_full_unstemmed | Leaders, followers, and community detection |
| title_short | Leaders, followers, and community detection |
| title_sort | leaders followers and community detection |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/91858 |
| work_keys_str_mv | AT parthasarathydhruuv leadersfollowersandcommunitydetection AT parthasarathydhruuv fastnonparametricdetectionofoverlappingcommunitiestheleaderfolloweralgorithm AT parthasarathydhruuv leaderfolloweralgorithm |