Statistics – Machine Learning
Scientific paper
2010-11-02
Statistics
Machine Learning
13 pages, 5 figures
Scientific paper
Traditional spectral clustering methods cannot naturally learn the number of communities in a network and often fail to detect smaller community structure in dense networks because they are based upon external community connectivity properties such as graph cuts. We propose an algorithm for detecting community structure in networks called the leader-follower algorithm which is based upon the natural internal structure expected of communities in social networks. The algorithm uses the notion of network centrality in a novel manner to differentiate leaders (nodes which connect different communities) from loyal followers (nodes which only have neighbors within a single community). Using this approach, it is able to naturally learn the communities from the network structure and does not require the number of communities as an input, in contrast to other common methods such as spectral clustering. We prove that it will detect all of the communities exactly for any network possessing communities with the natural internal structure expected in social networks. More importantly, we demonstrate the effectiveness of the leader-follower algorithm in the context of various real networks ranging from social networks such as Facebook to biological networks such as an fMRI based human brain network. We find that the leader-follower algorithm finds the relevant community structure in these networks without knowing the number of communities beforehand. Also, because the leader-follower algorithm detects communities using their internal structure, we find that it can resolve a finer community structure in dense networks than common spectral clustering methods based on external community structure.
Shah Devavrat
Zaman Tauhid
No associations
LandOfFree
Community Detection in Networks: The Leader-Follower Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Community Detection in Networks: The Leader-Follower Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Community Detection in Networks: The Leader-Follower Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-602125