基于连边密度传播的二分网络社区发现算法

依据节点在社区中的连边情况,定义社区内节点的连边密度,构造社区的平均密度评价指标。经过实例验证,社区的平均密度评价指标能够克服模块度在完全图上的分辨率限制。同时,通过节点的连边密度和最优化社区的平均密度,提出连边密度传播算法。在真实数据和人工数据上进行测试,利用该算法划分社区后求得的模块度和社区平均密度都比利用BRIM算法、边集聚系数算法和资源分布算法求得的值高。这表明相比以上三种算法,连边密度传播算法更能够有效地发现二分网络的社区结构。

COMMUNITY DISCOVERY ALGORITHM FOR BIPARTITE NETWORK BASED ON EDGE-TO-EDGE DENSITY PROPAGATION

According to the connection of nodes in the community, we defined the connection density of nodes in the community, and constructed the average density evaluation index of the community. The examples show that the average density evaluation index of community can overcome the resolution limitation of modularity on the complete graph. We proposed a edge-to-edge density propagation algorithm by optimizing the connection density of nodes and the average density of communities. The validation on real data and artificial data shows that the modularity and average density of community obtained by this algorithm is higher than that obtained by BRIM algorithm, edge clustering coefficient algorithm and resource distribution algorithm. The results show that compared with the above three algorithms, the algorithm is more effective in finding the community structure of the bipartite network.