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

文章基本信息

  • 标题:The Maximum Label Propagation Algorithm on Sparse Random Graphs
  • 本地全文:下载
  • 作者:Charlotte Knierim ; Johannes Lengler ; Pascal Pfister
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:145
  • 页码:1-15
  • DOI:10.4230/LIPIcs.APPROX-RANDOM.2019.58
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:In the Maximum Label Propagation Algorithm (Max-LPA), each vertex draws a distinct random label. In each subsequent round, each vertex updates its label to the label that is most frequent among its neighbours (including its own label), breaking ties towards the larger label. It is known that this algorithm can detect communities in random graphs with planted communities if the graphs are very dense, by converging to a different consensus for each community. In [Kothapalli et al., 2013] it was also conjectured that the same result still holds for sparse graphs if the degrees are at least C log n. We disprove this conjecture by showing that even for degrees n^epsilon, for some epsilon>0, the algorithm converges without reaching consensus. In fact, we show that the algorithm does not even reach almost consensus, but converges prematurely resulting in orders of magnitude more communities.
  • 关键词:random graphs; distributed algorithms; label propagation algorithms; consensus; community detection
国家哲学社会科学文献中心版权所有