Local community detection in dynamic graphs using personalized centrality
type: Item
instance of: scholarly article
title: Local community detection in dynamic graphs using personalized centrality
zbMATH Open document ID: 1433.68305
author: Eisha Nathan
author: Anita Zakrzewska
author: Jason Riedy
author: David A. Bader
published in: Algorithms
publication date: 2018-08-13T00:00:00Z
review text: Summary: Analyzing massive graphs poses challenges due to the vast amount of data available. Extracting smaller relevant subgraphs allows for further visualization and analysis that would otherwise be too computationally intensive. Furthermore, many real data sets are constantly changing, and require algorithms to update as the graph evolves. This work addresses the topic of local community detection, or seed set expansion, using personalized centrality measures, specifically PageRank and Katz centrality. We present a method to efficiently update local communities in dynamic graphs. By updating the personalized ranking vectors, we can incrementally update the corresponding local community. Applying our methods to real-world graphs, we are able to obtain speedups of up to \(60\times\) compared to static recomputation while maintaining an average recall of 0.94 of the highly ranked vertices returned. Next, we investigate how approximations of a centrality vector affect the resulting local community. Specifically, our method guarantees that the vertices returned in the community are the highly ranked vertices from a personalized centrality metric.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6916761
zbMATH Keywords: local community detection
zbMATH Keywords: dynamic graphs
zbMATH Keywords: personalized centrality metrics
describes a project that uses: DIMACS
describes a project that uses: KONECT
describes a project that uses: GenLouvain
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a10030102
OpenAlex ID: W2751435225
cites work: Q5691133
cites work: Community structure in social and biological networks
cites work: Q5298945
cites work: A new status index derived from sociometric analysis
cites work: On the Limiting Behavior of Parameter-Dependent Network Centrality Measures
cites work: CENTRALITY ESTIMATION IN LARGE NETWORKS
cites work: Q4414854
cites work: Fast unfolding of communities in large networks
cites work: Partitioning Sparse Matrices with Eigenvectors of Graphs
cites work: Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
cites work: Dynamic graph clustering combining modularity and smoothness
cites work: Estimating PageRank on graph streams
cites work: Updating Markov Chains with an Eye on Google's PageRank
cites work: Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
cites work: Iterative Refinement in Floating Point
DOI: 10.3390/A10030102
description: scientific article; zbMATH DE number 6916761