首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Modularity of Erdös-Rényi Random Graphs
  • 作者:Colin McDiarmid ; Fiona Skerman
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:110
  • 页码:31:1-31:13
  • DOI:10.4230/LIPIcs.AofA.2018.31
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q^*(G) (where 0 <= q^*(G)<= 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically. For the Erdös-Rényi random graph G_{n,p} with n vertices and edge-probability p, the likely modularity has three distinct phases. For np <= 1+o(1) the modularity is 1+o(1) with high probability (whp), and for np --> infty the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c_0 <= c_1 there exists delta>0 such that when c_0 <= np <= c_1 we have delta
  • 关键词:Community detection; Newman-Girvan Modularity; random graphs
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有