• 网站导航
学院动态
通知公告
学术活动
观点导读
最新资讯
统计数据
统计机构
统计资源
您现在的位置: 首页 > 观点导读 > 正文
探测二部图中社团结构的进化算法及其评论
[发布时间]:2012-09-12 [浏览次数]:

探测二部图中社团结构的进化算法及其评论

1. Evolutionary method for finding communities in bipartite networks, Phys. Rev. E 83, 066120 (2011)

Weihua Zhan, Zhongzhi Zhang, Jihong Guan, Shuigeng Zhou

Abstract: An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here,we show that the finding of communities in such networks can be unified in a general framework—detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rulewhich by incorporating related operations can guarantee the convergence of theMAGAto the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.

 

2. Comment on “Evolutionary method for finding communities in bipartite networks”, Phys. Rev. E 84, 058101 (2011)

Alberto Costa, Pierre Hansen

Abstract: In a recent paper, Zhan, Zhang, Guan, and Zhou [Phys. Rev. E 83, 066120 (2011)] presented a modified adaptive genetic algorithm (MAGA) tailored to the discovery of maximum modularity partitions of the node set into communities in unipartite, bipartite, and directed networks. The authors claim that “detection of communities in unipartite networks or in directed networks can be transformed into the same task in bipartite networks.” Actually, some tests show that it is not the case for the proposed transformations, and why. Experimental results of MAGA for modularity maximization of untransformed unipartite or bipartite networks are also discussed.

http://arxiv.org/abs/1011.3315

http://www.lix.polytechnique.fr/~costa/materiale/PRE_comm_2011_Costa.pdf

编者按: 欢迎那些对本文感兴趣的研究生和教师给编者写信, 提出您的宝贵意见或者评论. 我将及时地将您的建议反映在述评当中, 或者将您的评论放在本文后面. 邮箱是: zhyuanzh@gmail.com.

这两篇文章, 一篇文章提出了二部图中探测社团结构的一个进化算法, 而另一篇文章对此算法的有效性持不同意见, 比较阅读这两篇文章有助于我们更好地理解这一方向的进展.