• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >The Maximum Label Propagation Algorithm on Sparse Random Graphs
【24h】

The Maximum Label Propagation Algorithm on Sparse Random Graphs

机译：稀疏随机图上的最大标签传播算法

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 epsilon0, 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.
机译：在最大标签传播算法（Max-LPA）中，每个顶点绘制一个不同的随机标签。在随后的每个回合中，每个顶点将其标签更新为在其邻居中最频繁的标签（包括其自己的标签），从而断开与较大标签的联系。众所周知，如果算法非常密集，则该算法可以通过收敛到每个社区的不同共识来检测带有种植社区的随机图中的社区。在[Kothapalli et al。，2013]中，人们也猜想，如果度数至少为C log n，则对于稀疏图仍然会得到相同的结果。我们通过证明即使对于nεε度，对于某些ε> 0，该算法也收敛而没有达成共识。实际上，我们表明该算法甚至无法达成共识，但是过早收敛会导致更多数量级的社区。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号