Fast multi-scale detection of overlapping communities using local criteria
Fast multi-scale detection of overlapping communities using local criteria
复制标题
DOI：
10.1007/s00607-014-0401-1
复制
发表时间：
2014-11
期刊：
影响因子：
3.7
通讯作者：
Erwan Le Martelot;C. Hankin
中科院分区：
文献类型：
--
作者：
Erwan Le Martelot;C. Hankin
许多系统可以使用图形或网络来描述。检测这些网络中的社区可以提供有关原始系统的底层结构和功能的信息。然而，这种检测是一项复杂的任务，在过去的十年中为此投入了大量的工作。一个重要的特征是，可以在多种规模或分辨率级别上找到社区，这表明了组织的多个级别。因此，一个图可能有多个社区结构。此外，网络往往很大，因此需要高效的处理。在这项工作中，我们提出了一种具有线性复杂度的新算法，用于使用局部标准快速检测跨尺度的社区。我们利用该标准的局部方面来实现并行计算并进一步提高执行速度。该算法针对非常大的生成的多尺度网络进行了测试，实验证明了其效率和准确性。
Many systems can be described using graphs, or networks. Detecting communities in these networks can provide information about the underlying structure and functioning of the original systems. Yet this detection is a complex task and a large amount of work was dedicated to it in the past decade. One important feature is that communities can be found at several scales, or levels of resolution, indicating several levels of organisation. Therefore a graph may have several community structures. Also networks tend to be large and hence require efficient processing. In this work, we present a new algorithm with linear complexity for the fast detection of communities across scales using a local criterion. We exploit the local aspect of the criterion to enable parallel computation and improve the execution speed further. The algorithm is tested against very large generated multi-scale networks and experiments demonstrate its efficiency and accuracy.