Detecting genuine communities from large-scale social networks: A pattern-based method

Community detection is a long-standing yet very difficult task in social network analysis. It becomes more challenging as many online social networking sites are evolving into super-large scales. Numerous methods have been proposed for community detection from massive networks, but how to reconcile the partitioning efficiency and the community quality remains an open problem. In this paper, we attempt to address this challenge by introducing a COSine-pattern-based COMmunity extraction framework: COSCOM.TheCOSCOMadopts an extracting view of community detection. It first extracts the so-called asymptotically equivalent structures (AESs) from networks, from which the nodes are further partitioned into crisp communities using any of the existing methods. Specifically, we prove that anAESis a very tight group of nodes, and is actually a cosine pattern defined by the extended cosine similarity.A novel cosine-pattern mining algorithm based on the ordered antimonotone of cosine similarity is thus proposed for the efficient extraction of AESs. Experiments on various real-world social networks demonstrate the advantage of the extracting view of community detection. In particular, COSCOM shows merits in detecting genuine communities by either internal or external validity.