Finding community structure in networks using the eigenvectors of matrices. Export

@article{citeulike:1127152, abstract = {We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.}, address = {Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA.}, author = {Newman, M. E.}, citeulike-article-id = {1127152}, citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/17025705}, citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=17025705}, citeulike-linkout-2 = {http://dx.doi.org/10.1103/PhysRevE.74.036104}, doi = {10.1103/PhysRevE.74.036104}, issn = {1539-3755}, journal = {Phys Rev E Stat Nonlin Soft Matter Phys}, keywords = {centrality, communities, coordinate-systems, eigenvectors, iff, invariances, linguistic-frameworks, local, locales, locality, modularity, modules, network-analysis, network-equations, networks, pagerank, reference-frames, social-networks, social-structures, stationarity}, month = {September}, number = {3 Pt 2}, posted-at = {2009-06-07 22:04:51}, priority = {2}, title = {Finding community structure in networks using the eigenvectors of matrices.}, url = {http://dx.doi.org/10.1103/PhysRevE.74.036104}, volume = {74}, year = {2006} }

TY - JOUR ID - citeulike:1127152 L3 - citeulike-article-id:1127152 N2 - We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks. IS - 3 Pt 2 JF - Phys Rev E Stat Nonlin Soft Matter Phys SN - 1539-3755 AD - Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA. TI - Finding community structure in networks using the eigenvectors of matrices. VL - 74 KW - centrality KW - communities KW - coordinate-systems KW - eigenvectors KW - iff KW - invariances KW - linguistic-frameworks KW - local KW - locales KW - locality KW - modularity KW - modules KW - network-analysis KW - network-equations KW - networks KW - pagerank KW - reference-frames KW - social-networks KW - social-structures KW - stationarity AU - Newman, ME PY - 2006/09// UR - http://dx.doi.org/10.1103/PhysRevE.74.036104 ER -