一种新的社团挖掘算法MFA

　　摘要：介绍了一种新的社团挖掘算法MFA（MaximumweightededgeFirstAlgorithm），该算法是一个优先考虑边权值进行社团划分的算法，同时也继承了通过优化Q值进行社团划分的算法的优点。通过实验证明，该算法完全正确的将加权的Zachary网络划分为个数分别为16和18的两个社团，要远优于其他大部分社团划分算法。

　　关键词：社团挖掘；算法；MFA

　　中图分类号：TP301.6文献标识码：A文章编号：1009-3044（2013）36-8217-03

　　1概述

　　目前，通过直接优化模块Q值来进行社团划分的算法以其稳定而良好的表现在社团挖掘领域占据了主导地位。相关的文献也指明，在加权网络的社团挖掘方面，模块Q值同样是一个优秀的判断和划分标准。但是直接优化Q值的方式也并不是完美无缺的，分析基于这种方式的现有加权网络社团划分算法不难发现：它们往往忽视了边权值这一加权网络最重要的特殊属性，而试图将之视为普通的复杂网络而加以处理。这正是现有算法的先天缺陷之一[1-4]。

　　MFA算法是一个优先考虑边权值进行社团划分的算法，同时也继承了通过优化Q值进行社团划分的算法的优点。该算法是基于Newman快速算法加以改进的，其时间复杂度达到了[O（n2）]，并且有进一步提高的余地。

　　2MFA算法思想

　　观察现实的社会生活，我们会发现：判断一个个体是否在某一个群体中，往往是根据这个个体和群体中其他个体的交往次数的多少来判断的，交往次数越多，这个个体在群体中的可能性就越大。如果用网络来表现这一现象。个体就相当于网络中的节点；个体之间的交往次数就相当于在节点之间的边上加权；个体加入了群体就相当于进行了社团划分。联系社团划分这个目的仔细的分析这个现象，我们会找到这样几

　　个关键所在：要形成一个群体的关键是要有足够多的相互联系，而足够多的相互联系本身就是群体形成的一个重要因素。

　　在加权网络社团划分过程中，单纯的考虑权值会造成一个显而易见的问题，那就是网络中的所有节点会按照边权值的大小一次合并到同一个社团中，这个结果显然不是我们所需要的。那么，现在的问题就是，当我们找到了一个权值最大的边是，如何判断这条边所联系的两个顶点是属于同一个社团的呢？显然，模块Q值在这里为我们提供了足够有力的判断标准。在此我们采用Newman快速算法的标准，以合并后△Q是否大于0来决定合并与否。

　　此时，我们发现，MFA算法的基本思想已经形成了，它的流程如图1所示。

　　3MFA算法的实验分析