Targeted revision: A learning-based approach for incremental community detection in dynamic networks

Jiaxing Shang, Lianchen Liu, Xin Li, Feng Xie and Cheng Wu

Physica A: Statistical Mechanics and its Applications, 2016, vol. 443, issue C, 70-85

Abstract: Community detection is a fundamental task in network analysis. Applications on massive dynamic networks require more efficient solutions and lead to incremental community detection, which revises the community assignments of new or changed vertices during network updates. In this paper, we propose to use machine learning classifiers to predict the vertices that need to be inspected for community assignment revision. This learning-based targeted revision (LBTR) approach aims to improve community detection efficiency by filtering out the unchanged vertices from unnecessary processing. In this paper, we design features that can be used for efficient target classification and analyze the time complexity of our framework. We conduct experiments on two real-world datasets, which show our LBTR approach significantly reduces the computational time while keeping a high community detection quality. Furthermore, as compared with the benchmarks, we find our approach’s performance is stable on both growing networks and networks with vertex/edge removals. Experiments suggest that one should increase the target classification precision while keeping recall at a reasonable level when implementing our proposed approach. The study provides a unique perspective in incremental community detection.

Keywords: Incremental community detection; Dynamic networks; Targeted revision; Computational complexity (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437115008080
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:443:y:2016:i:c:p:70-85

DOI: 10.1016/j.physa.2015.09.072

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().