Fast detection of community structures using graph traversal in social networks
Fast detection of community structures using graph traversal in social networks
复制标题
DOI：
10.1007/s10115-018-1209-7
复制
发表时间：
2019-04-01
影响因子：
2.7
通讯作者：
Majumder, Subhashis
中科院分区：
文献类型：
--
作者：
Basuchowdhuri, Partha;Sikdar, Satyaki;Majumder, Subhashis
在社交网络中寻找社区结构被认为是一项具有挑战性的任务，因为许多提出的算法计算成本很高，并且对于大图来说不能很好地扩展。迄今为止提出的大多数社区检测算法都不适合需要实时检测社区的应用，特别是对于大规模网络。 Louvain 方法使用模块化最大化来检测集群，通常被认为是最快的社区检测算法之一，即使其运行时间没有任何可证明的限制。我们提出了一种新颖的基于图遍历的社区检测框架，它不仅比 Louvain 方法运行得更快，而且还能为大多数基准数据集生成质量更好的集群。我们展示了我们的算法在 O(|V|+|E|) 时间内运行以创建初始覆盖，然后使用模块化最大化来获得最终覆盖。
Finding community structures in social networks is considered to be a challenging task as many of the proposed algorithms are computationally expensive and does not scale well for large graphs. Most of the community detection algorithms proposed till date are unsuitable for applications that would require detection of communities in real time, especially for massive networks. The Louvain method, which uses modularity maximization to detect clusters, is usually considered to be one of the fastest community detection algorithms even without any provable bound on its running time. We propose a novel graph traversal-based community detection framework, which not only runs faster than the Louvain method but also generates clusters of better quality for most of the benchmark datasets. We show that our algorithms run in O(|V|+|E|) time to create an initial cover before using modularity maximization to get the final cover.