An incremental batch technique for community detection

In the analysis of real world networks, it is often of interest to partition nodes into groups referred to as communities, whereby each community is densely connected and different communities are sparsely connected to one another. While community detection on static networks has been extensively re...

Full description

Saved in:
Bibliographic Details
Main Authors: Wen Haw Chong, Loo Nin Teow
Format: Conference Proceeding
Language:English
Subjects:
Accuracy
Communities
Community Detection
Complex Networks
Computational efficiency
Image edge detection
Incremental Update
Merging
Modularity
Optimization
Social network services
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the analysis of real world networks, it is often of interest to partition nodes into groups referred to as communities, whereby each community is densely connected and different communities are sparsely connected to one another. While community detection on static networks has been extensively researched on, updating community structures efficiently and accurately on evolving networks is a relatively new research area. In this paper, we discuss the inadequacies of previous techniques as well as justify the need for a new class of techniques that can handle complex batch changes in networks. We then propose one such incremental technique. Compared to earlier work, the proposed technique is much more efficient in scenarios where a network evolves significantly while maintaining a high level of accuracy. Experiments on both artificial and real world networks validate the utility of the proposed technique.