标题： 使用Fortunato性能度量的社区检测 显示英文标题

标题： Community Detection using Fortunato's Performance Measure

摘要： 在他关于社区检测的论文[1]中，Fortunato引入了一个称为性能的质量函数，用于评估图划分的好坏。 该度量计算了被正确“解释”的顶点对的数量，即属于同一社区且由边连接的两个顶点，或者属于不同社区且没有由边连接的两个顶点。 在本文中，我们探讨了Fortunato的性能度量（fp度量）用于检测无权、无向网络中的社区。 首先，我们给出一个贪心算法fpGreed，它通过在两个层次上迭代工作来尝试优化fp度量，即顶点层次和社区层次。 在顶点层次，只有当fp值改善时，一个顶点才会加入一个社区。 一旦完成此步骤，将获得初始的一组社区。 在下一步中，只有当fp度量改善时，两个社区才会合并。 一旦没有进一步的改进，算法将返回到顶点层次，如此反复。 当任何社区都没有变化时，fpGreed终止。 然后，我们提出一个更快的启发式算法fastFp，更适合在大型数据集上运行。 我们在几个著名的数据集上展示了社区的质量以及计算它们所需的时间。 对于一些大型数据集，如youtube和livejournal，我们发现Algorithm fastFP在计算时间和获得的解决方案质量方面都表现非常好。 显示英文摘要

摘要： In his paper on Community Detection [1], Fortunato introduced a quality function called performance to assess the goodness of a graph partition. This measure counts the number of correctly ``interpreted" pairs of vertices, i. e. two vertices belonging to the same community and connected by an edge, or two vertices belonging to different communities and not connected by an edge. In this paper, we explore Fortunato's performance measure (fp measure) for detecting communities in unweighted, undirected networks. First, we give a greedy algorithm fpGreed that tries to optimise the fp measure by working iteratively at two-levels, vertex-level and community-level. At the vertex level, a vertex joins a community only if the fp value improves. Once this is done, an initial set of communities are obtained. At the next stage, two communities merge only if the fp measure improves. Once there are no further improvements to be made, the algorithm switches back to the vertex level and so on. fpGreed terminates when there are no changes to any community. We then present a faster heuristic algorithm fastFp more suitable for running on large datasets. We present the quality of the communities and the time it takes to compute them on several well-known datasets. For some of the large datasets, such as youtube and livejournal, we find that Algorithm fastFP performs really well, both in terms of the time and the quality of the solution obtained.