research-article

The interplay between dynamics and networks: centrality, communities, and cheeger inequality

Authors:

Shang-hua Teng,

Kristina Lerman,

Xiaoran YanAuthors Info & Claims

KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 1406 - 1415

https://doi.org/10.1145/2623330.2623738

Published: 24 August 2014 Publication History

Abstract

We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This framework generalizes the traditional Laplacian framework to continuous-time biased random walks and also allows us to model some epidemic processes over a network. For each dynamic process in our framework, we can define a function that measures the quality of every subset of nodes as a potential cluster (or community) with respect to this process on a given network. This subset-quality function generalizes the traditional conductance measure for graph partitioning. We partially justify our choice of the quality function by showing that the classic Cheeger's inequality, which relates the conductance of the best cluster in a network with a spectral quantity of its Laplacian matrix, can be extended from the Laplacian-conductance setting to this more general setting.

Supplementary Material

MP4 File (p1406-sidebyside.mp4)

Download
288.66 MB

References

[1]

L. A. Adamic and N. Glance. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36--43. ACM, 2005.

Digital Library

[2]

R. Andersen, F. Chung, and K. Lang. Using PageRank to Locally Partition a Graph. Internet Math., 4(1):1--128, 2007.

[3]

R. Andersen and Y. Peres. Finding Sparse Cuts Locally Using Evolving Sets. In STOC, pages 235--244. ACM, 2009.

Digital Library

[4]

P. Bonacich and P. Lloyd. Eigenvector-like measures of centrality for asymmetric relations. Social Networks, 23(3):191--201, 2001.

[5]

S. Borgatti. Centrality and network flow. Social Networks, 27(1):55--71, Jan. 2005.

[6]

F. Chung. The heat kernel as the pagerank of a graph. Proceedings of the National Academy of Sciences, 104(50):19735--19740, Dec. 2007.

[7]

F. Chung. A local graph partitioning algorithm using heat kernel pagerank. Internet Mathematics, 6(3):315--330, Jan. 2009.

[8]

F. R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, Feb. 1997.

[9]

J.-C. Delvenne, S. N. Yaliraki, and M. Barahona. Stability of graph communities across time scales. ArXiv e-prints, Dec. 2008.

[10]

R. Ghosh and K. Lerman. Parameterized centrality metric for network analysis. Physical Review E, 83(6):066118, June 2011.

[11]

M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved. In STOC, pages 235--244. ACM, 1988.

Digital Library

[12]

R. Kannan, S. Vempala, and A. Vetta. On Clusterings: Good, Bad and Spectral. J. ACM, 51(3):497--515, May 2004.

Digital Library

[13]

D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD '03, pages 137--146. ACM, 2003.

Digital Library

[14]

I. Koutis, G. L. Miller, and R. Peng. Approaching Optimality for Solving SDD Linear Systems. In FOCS, pages 235--244. IEEE, 2010.

Digital Library

[15]

R. Lambiotte, R. Sinatra, J.-C. Delvenne, T. S. Evans, M. Barahona, and V. Latora. Flow graphs: Interweaving dynamics and structure.textbackslashpre, 84(1):017102, July 2011.

[16]

K. Lerman and R. Ghosh. Network Structure, Topology and Dynamics in Generalized Models of Synchronization. Physical Review E, 86(026108), 2012.

[17]

L. Lovász. Random Walks on Graphs: A Survey, pages 353--397. 1993.

[18]

J. J. McAuley and J. Leskovec. Learning to Discover Social Circles in Ego Networks. In NIPS, volume 272, pages 548--556, 2012.

Digital Library

[19]

M. E. J. Newman. Finding community structer in networks using the eigenvectors of matrices. Physical Review E, 74(3), 2006.

[20]

L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web, 1999.

[21]

K. Poole. Voteview Website. http://voteview.com/house98.htm.

[22]

M. Rosvall and C. T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4):1118--1123, Jan. 2008.

[23]

J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000.

Digital Library

[24]

L. M. Smith, K. Lerman, C. Garcia-Cardona, A. G. Percus, and R. Ghosh. Spectral Clustering with Epidemic Diffusion. CoRR, abs/1303.2663, 2013.

[25]

D. A. Spielman and S.-H. Teng. Spectral partitioning works: Planar graphs and finite element meshes. In IEEE FOCS, pages 96--105, 1996.

Digital Library

[26]

D. A. Spielman and S.-H. Teng. Nearly-linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems. In STOC, pages 81--90. ACM, 2004.

Digital Library

[27]

Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos. Epidemic spreading in real networks: an eigenvalue viewpoint. In Proceedings of the 22nd Symposium on Reliable Distributed Systems, pages 25--34, Los Alamitos, CA, USA, Oct. 2003. IEEE.

[28]

D. J. Watts and S. H. Strogatz. Collective dynamics of łqsmall-world rqnetworks. nature, 393(6684):440--442, 1998.

[29]

M. A. Yildirim, K.-I. Goh, M. E. Cusick, A.-L. Barabasi, and M. Vidal. Drug-target network. Nat Biotech, 25:1119--1126, Oct. 2007.

[30]

W. W. Zachary. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 33(4):452--473, 1977.

Cited By

Eubank S(2024)Does Isolating High-Modularity Communities Prevent Cascading Failure?Complex Networks & Their Applications XII10.1007/978-3-031-53499-7_4(43-54)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-3-031-53499-7_4
Pellegrina LSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Efficient Centrality Maximization with Rademacher AveragesProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599325(1872-1884)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599325
Mishra REubank SNath MAmundsen MAdiga A(2023)Community Detection Using Moore-Shannon Network Reliability: Application to Food NetworksComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_21(271-282)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-21131-7_21
Show More Cited By

Index Terms

The interplay between dynamics and networks: centrality, communities, and cheeger inequality
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation theory
      1. Systems theory
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Information theory

Recommendations

Fast centrality approximation in modular networks
CNIKM '09: Proceedings of the 1st ACM international workshop on Complex networks meet information & knowledge management

Measuring the centrality of nodes in real-world networks has remained an important task in the technological, social, and biological network paradigms carrying implications on their analysis and applications. Exact inference of centrality values is ...
An improved algorithm for detecting overlapping communities in social network

Social networks contain hidden communities, which used to have some structure and the effort to discover those structures of the communities is a significant step in analysing the large-scale structure of those networks. Till now many algorithms have ...
Centrality-based bipartite local community detection algorithm
ICC '17: Proceedings of the Second International Conference on Internet of things, Data and Cloud Computing

As a kind of typical complex network, bipartite network has already received many specialized research. Local community detection is very useful for bipartite network, but it has not yet been systematically researched. To guarantee equivalent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2014

2028 pages

ISBN:9781450329569

DOI:10.1145/2623330

General Chairs:
Sofus Macskassy
Facebook
,
Claudia Perlich
Dstillery
,
Program Chairs:
Jure Leskovec
Stanford University
,
Wei Wang
UCLA
,
Rayid Ghani
University of Chicago

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

KDD '14

Sponsor:

KDD '14: The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2014

New York, New York, USA

Acceptance Rates

KDD '14 Paper Acceptance Rate 151 of 1,036 submissions, 15%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
754
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Eubank S(2024)Does Isolating High-Modularity Communities Prevent Cascading Failure?Complex Networks & Their Applications XII10.1007/978-3-031-53499-7_4(43-54)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-3-031-53499-7_4
Pellegrina LSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Efficient Centrality Maximization with Rademacher AveragesProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599325(1872-1884)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599325
Mishra REubank SNath MAmundsen MAdiga A(2023)Community Detection Using Moore-Shannon Network Reliability: Application to Food NetworksComplex Networks and Their Applications XI10.1007/978-3-031-21131-7_21(271-282)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-21131-7_21
Xia FWang LTang TChen XKong XOatley GKing I(2022)CenGCN: Centralized Convolutional Networks with Vertex Imbalance for Scale-Free GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3149888(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3149888
Liu MGleich DLarochelle HRanzato MHadsell RBalcan MLin H(2020)Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clusteringProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496146(5023-5035)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496146
Rosell-Tarragó GDíaz-Guilera A(2020)Functionability in complex networks: Leading nodes for the transition from structural to functional networks through remote asynchronizationChaos: An Interdisciplinary Journal of Nonlinear Science10.1063/1.509962130:1Online publication date: 6-Jan-2020
https://doi.org/10.1063/1.5099621
Chen WTeng SZhang H(2020)A graph-theoretical basis of stochastic-cascading network influence: Characterizations of influence-based centralityTheoretical Computer Science10.1016/j.tcs.2020.04.016824-825(92-111)Online publication date: Jul-2020
https://doi.org/10.1016/j.tcs.2020.04.016
Li HPeng RShan LYi YZhang Z(2019)Current Flow Group Closeness Centrality for Complex Networks?The World Wide Web Conference10.1145/3308558.3313490(961-971)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313490
Ibrahim RGleich D(2019)Nonlinear Diffusion for Community Detection and Semi-Supervised LearningThe World Wide Web Conference10.1145/3308558.3313483(739-750)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313483
Rosell-Tarragó GCozzo EDíaz-Guilera A(2018)A Complex Network Framework to Model CognitionComplexity10.1155/2018/19187532018Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1155/2018/1918753
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents