Paper Info
Title
Local Fiedler vector centrality for detection of deep and overlapping communities in networks
Abstract
In this paper, a new centrality called local Fiedler vector centrality (LFVC) is proposed to analyze the connectivity structure of a graph. It is associated with the sensitivity of algebraic connectivity to node or edge removals and features distributed computations via the associated graph Laplacian matrix. We prove that LFVC can be related to a monotonic submodular set function that guarantees that greedy node or edge removals come within a factor 1-1/e of the optimal non-greedy batch removal strategy. Due to the close relationship between graph topology and community structure, we use LFVC to detect deep and overlapping communities on real-world social network datasets. The results offer new insights on community detection by discovering new significant communities and key members in the network. Notably, LFVC is also shown to significantly outperform other well-known centralities for community detection.
Year
DOI
Venue
2014
10.1109/ICASSP.2014.6853771
ICASSP
Keywords
Field
DocType
laplace equations,greedy node,local fiedler vector centrality,algebraic connectivity,matrix algebra,optimal nongreedy batch removal strategy,lfvc,deep network community detection,associated graph laplacian matrix,community structure,monotonic submodular set function,distributed computations,real-world social network datasets,graph theory,social networking (online),graph topology,edge removals,overlapping network community detection,vectors
Network science,Spectral graph theory,Computer science,Theoretical computer science,Artificial intelligence,Laplacian matrix,Pattern recognition,Submodular set function,Centrality,Algebraic connectivity,Connectivity,Topological graph theory,Machine learning
Conference
ISSN
Citations 
PageRank 
1520-6149
5
0.53
References 
Authors
0
2
Name
Order
Citations
PageRank
Pin-Yu Chen164674.59
Alfred O. Hero III22600301.12