K-Hop Community Search Based On Local Distance Dynamics = K-Hop Community Search Based On Local Distance Dynamics

다국어 초록 (Multilingual Abstract)

Community search aims at finding a meaningful community that contains the query node and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. However, most metric-based algorithms tend to include irrelevant subgraphs in the identified community. Apart from the user-defined metric algorithm, how can we search the natural community that the query node belongs to? In this paper, we propose a novel community search algorithm based on the concept of the k-hop and local distance dynamics model, which can naturally capture a community that contains the query node. The basic idea is to envision the nodes that k-hop away from the query node as an adaptive local dynamical system, where each node only interacts with its local topological structure. Relying on a proposed local distance dynamics model, the distances among nodes change over time, where the nodes sharing the same community with the query node tend to gradually move together, while other nodes stay far away from each other. Such interplay eventually leads to a steady distribution of distances, and a meaningful community is naturally found. Extensive experiments show that our community search algorithm has good performance relative to several state-of-the-art algorithms.

참고문헌 (Reference)

1 Palla G, "Uncovering the overlapping community structure of complex networks in nature and society" 435 (435): 814-818, 2005

2 Wang J, "Truss decomposition in massive networks" 5 (5): 812-823, 2012

3 Huang J, "Towards online multiresolution community detection in large-scale networks" 6 (6): e23829-, 2011

4 Zhou X, "Top k Favorite Probabilistic Products Queries" 28 (28): 2808-2821, 2016

5 Sozio M, "The community-search problem and how to plan a successful cocktail party" 939-948, 2010

6 Barahona M, "Synchronization in small-world systems" 89 (89): 54-101, 2002

7 Ugander J, "Structural diversity in social contagion" 109 (109): 5962-5966, 2012

8 Xu X, "Scan: a structural clustering algorithm for networks" 824-833, 2007

9 Wu Y, "Robust local community detection: on free rider effect and its elimination" 8 (8): 798-809, 2015

10 Huang X, "Querying k-truss community in large and dynamic graphs" 1311-1322, 2014

11 Liu Q, "Preserving privacy with probabilistic indistinguishability in weighted social networks" 28 (28): 1417-1429, 2017

12 Xie J, "Overlapping community detection in networks: The state-of-the-art and comparative study" 45 (45): 1-35, 2013

13 Raghavan U N, "Near linear time algorithm to detect community structures in large-scale networks" 76 (76): 36-106, 2007

14 Luo J, "Motif discovery using an immune genetic algorithm" 264 (264): 319-325, 2010

15 Newman M E J, "Modularity and community structure in networks" 103 (103): 8577-8582, 2006

16 Cui W, "Local search of communities in large graphs" 991-1002, 2014

17 Li R H, "Influential community search in large networks" 8 (8): 509-520, 2015

18 Edachery J, "Graph clustering using distance-k cliques" 98-106, 1999

19 Newman M E J, "Finding and evaluating community structure in networks" 69 (69): 26-113, 2004

20 Cheng J, "Fast algorithms for maximal clique enumeration with limited memory" 1240-1248, 2012

21 Chang L, "Efficiently computing k-edge connected components via graph decomposition" 205-216, 2013

22 Xiao G, "Efficient top-(k, l) range query processing for uncertain data based on multicore architectures" 33 (33): 381-413, 2015

23 Lancichinetti A, "Detecting the overlapping and hierarchical community structure in complex networks" 11 (11): 15-33, 2009

24 Fortunato S, "Community detection in graphs" 486 (486): 75-174, 2010

25 Shao J, "Community detection based on distance dynamics" 1075-1084, 2015

26 Watts D J, "Collective dynamics of 'small-world' networks" 393 (393): 440-442, 1998

27 Kunze M, "Behavioral similarity-a proper metric" 166-181, 2011

28 Huang X, "Approximate closest community search in networks" 9 (9): 276-287, 2015

29 Zhang S, "Anonymizing popularity in online social networks with full utility" 72 (72): 227-238, 2017

30 Lipkus A H, "A proof of the triangle inequality for the Tanimoto distance" 26 (26): 263-265, 1999