• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

K-Hop Community Search Based On Local Distance Dynamics

Vol. 12, No.7, July 31, 2018
10.3837/tiis.2018.07.005 , Download Paper (Free):

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.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Tao Meng, Lijun Cai, Tingqin He, Lei Chen and Ziyun Deng, "K-Hop Community Search Based On Local Distance Dynamics," KSII Transactions on Internet and Information Systems, vol. 12, no. 7, pp. 3041-3063, 2018. DOI: 10.3837/tiis.2018.07.005

[ACM Style]
Meng, T., Cai, L., He, T., Chen, L., and Deng, Z. 2018. K-Hop Community Search Based On Local Distance Dynamics. KSII Transactions on Internet and Information Systems, 12, 7, (2018), 3041-3063. DOI: 10.3837/tiis.2018.07.005