Near linear time algorithm to detect community structures in large-scale networks

Details Near linear time algorithm to detect community structures in large-scale networks Near linear time algorithm to detect community structures in large-scale networks

2007-09-19

arxiv.org/abs/0709.2938v1

Physical Review E 76, 036106 (2007)

Physics

Physics and Society

12 pages, 9 figures

Scientific paper

10.1103/PhysRevE.76.036106

Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a pre-defined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.

Affiliated with

Also associated with

No associations

Rating

Near linear time algorithm to detect community structures in large-scale networks 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 Near linear time algorithm to detect community structures in large-scale networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near linear time algorithm to detect community structures in large-scale networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-336198