Abstract：To find top-K relative communities associated with the query point is of significance in practical research . In this paper, the concept of clique and relative community is defined, and a method to rapidly detect the top-K relative communities is explored. A down detection expansion algorithm is proposed. All the clique structures are detected from query point. By extending each clique structure outward to construct a community, the top-K relative communities of the query point is quickly acquired through loop iteration. Meanwhile, to reduce the searching space and computing time, the down detection expansion algorithm is improved. Through comprehensive experimental comparison, the validity of the original algorithm and the efficiency of improved algorithm is verified.
[1] Bakshy E, Rosenn I, Marlow C, et al. The Role of Social Networks in Information Diffusion // Proc of the 21st International World Wide Web Conference. Lyon, France, 2012: 519-528 [2] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E, 2004. DOI: 10.1103/PhysRevE.69.066133 [3] Zhao Y P, Levina E, Zhu J. Community Extraction for Social Networks. Proceedings of the National Academy of Sciences of the Uni-ted States of America, 2011, 108(18): 7321-7326 [4] Cui W Y, Xiao Y H, Wang H X, et al. Online Search of Overla-pping Communities // Proc of the ACM SIGMOD International Conference on Management of Data. New York, USA, 2013: 277-288 [5] Liu S Y, Wang S H, Zhu F D, et al. Hydra: Large-Scale Social Identity Linkage via Heterogeneous Behavior Modeling // Proc of the ACM SIGMOD International Conference on Management of Data. Snowbird, USA, 2014: 51-62 [6] Qiao M, Qin L, Cheng H, et al. Top-K Nearest Keyword Search on Large Graphs // Proc of the 39th International Conference on Very Large Data Bases. Riva del Garda, Italy, 2013: 901-912 [7] Palla G, Barabási A L, Vicsek T. Quantifying Social Group Evolution. Nature, 2007, 446(7136): 664-667 [8] Baumes J, Goldberg M, Krishnamoorthy M, et al. Finding Communities by Clustering a Graph into Overlapping Subgraphs // Proc of the IADIS International Conference on Applied Computing. Algarve, Portugal, 2005, II: 97-104 [9] Ahn Y Y, Bagrow J P, Lehmann S. Link Communities Reveal Multiscale Complexity in Networks. Nature, 2010, 466(7307): 761-764 [10] Kumpula J M, Kivel M, Kaski K, et al. Sequential Algorithm for Fast Clique Percolation. Physical Review E, 2008. DOI: 10.1103/PhysRevE.78.026109 [11] Newman M E J. The Structure and Function of Complex Networks[EB/OL]. [2014-05-30]. http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf
2015, Vol. 28 
