Spectral properties of modularity matrices

详细信息    查看全文

• 作者：Marianna Bolla^a ; ^{marib@math.bme.hu" class="auth_mail" title="E-mail the corresponding author} ; Brian Bullins^b ; ^{bbullins@cs.princeton.edu" class="auth_mail" title="E-mail the corresponding author} ; Sorathan Chaturapruek^c ; ^{tummykung@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Shiwen Chen^d ; ^{s.heidi.chen@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Katalin Friedl^e ; ^{friedl@cs.bme.hu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50 ; 62H17
• 刊名：Linear Algebra and its Applications
• 出版年：2015
• 出版时间：15 May 2015
• 年：2015
• 卷：473
• 期：Complete
• 页码：359-376
• 全文大小：391 K

文摘

There is an exact relation between the spectra of modularity matrices introduced in social network analysis and the an id="mmlsi1" class="mathmlsrc">an class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379514007186&_mathId=si1.gif&_user=111111111&_pii=S0024379514007186&_rdoc=1&_issn=00243795&md5=a31104832035f3321568669955152d7b" title="Click to view the MathML source">χ²an>an class="mathContainer hidden">an class="mathCode">ath altimg="si1.gif" overflow="scroll">χ2ath>an>an>an> statistic. We investigate a weighted graph with the main interest being when the hypothesis of independent attachment of the vertices is rejected, and we look for clusters of vertices with higher inter-cluster relations than expected under the hypothesis of independence. In this context, we give a sufficient condition for a weighted, and a sufficient and necessary condition for an unweighted graph to have at least one positive eigenvalue in its modularity or normalized modularity spectrum, which guarantees a community structure with more than one cluster. This property has important implications for the isoperimetric inequality, the symmetric maximal correlation, and the Newman–Girvan modularity.