Incremental community discovery via latent network representation and probabilistic inference

Zhe Cui, Noseong Park, Tanmoy Chakraborty

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Most of the community detection algorithms assume that the complete network structure G= (V, E) is available in advance for analysis. However, in reality this may not be true due to several reasons, such as privacy constraints and restricted access, which result in a partial snapshot of the entire network. In addition, we may be interested in identifying the community information of only a selected subset of nodes (denoted by VT⊆ V), rather than obtaining the community structure of all the nodes in G. To this end, we propose an incremental community detection method that repeats two stages—(i) network scan and (ii) community update. In the first stage, our method selects an appropriate node in such a way that the discovery of its local neighborhood structure leads to an accurate community detection in the second stage. We propose a novel criterion, called Information Gain, based on existing network embedding algorithms (Deepwalk and node2vec) to scan a node. The proposed community update stage consists of expectation–maximization and Markov Random Field-based denoising strategy. Experiments with 5 diverse networks with known ground-truth community structure show that our algorithm achieves 10.2% higher accuracy on average over state-of-the-art algorithms for both network scan and community update steps.

Original languageEnglish
Pages (from-to)2281-2300
Number of pages20
JournalKnowledge and Information Systems
Issue number6
Publication statusPublished - 2020 Jun 1

Bibliographical note

Funding Information:
T. Chakraborty would like to acknowledge the support of Ramanujan Fellowship, Early Career Research Award (ECR/2017/001691) (SERB, DST) and the centre for Design and New Media (supported by TCS), IIIT-Delhi. Noseong Park is the corresponding author. 1 In this paper, we consider disjoint communities around the target nodes. 2 A private node does not allow others to access its profile. Therefore, we cannot directly scan a private node. 3 For efficiency, we allow to scan multiple nodes in an iteration.

Publisher Copyright:
© 2019, The Author(s).

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Incremental community discovery via latent network representation and probabilistic inference'. Together they form a unique fingerprint.

Cite this