A self-organized approach for detecting communities in networks

The community structure of networks reveals hidden information about the whole network structure that cannot be discerned using other topological properties. Yet, the importance of identifying community structure in networks to many fields such as medicine, social sciences and national security, calls for better approaches for performing the identification. The prevalent community detection algorithms utilize a centralized approach that is unlikely to scale to very large networks and does not handle dynamic networks. We propose a self-organized approach to community detection which utilizes a newly introduced concept of node entropy to allow individual nodes to make decentralized and independent decisions concerning the community to which they belong; we call our approach Self-Organized Community Identification ALgorithm (SOCIAL). Node entropy is a mathematical expression of an individual node’s satisfaction with its current community. As nodes become more “satisfied”, i.e., entropy is low, the community structure of a network is emergent. Our algorithm offers several advantages over existing algorithms including near-linear performance, identification of partial community overlaps, and handling of dynamic changes in the network in a local manner. © 2014, Springer-Verlag Wien.