摘要：介绍了一种新的社团挖掘算法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算法的实验分析

　　3.1算法复杂度分析

　　整个算法包括三个部分：初始化、查找、合并。

　　其中查找的时间复杂度为[O（m）]；每次合并以后，更新相应的元素[eij]，[eki]，[ekj]（k≠i，j），[ai]，[aj]，该步的时间复杂度为[O（n）]。因此，一次查找和合并的总时间复杂度为[O（m+n）]。对于一个n个顶点的网络来说，共需要进行n-2次合并，因此算法总的时间复杂度为[O（（m+n）n）]。对于稀疏网络，时间复杂度为[O（n2）]。

　　3.2实验对比

　　由于找不到更多的最新算法，我们选择了目前世界上性能较好的加权Newman快速算法与本算法进行了对比。

　　由于目前加权网络方面的研究较少，因此加权网络的实验数据集也比较少。限于此种情况，我们采取了一部分无权网络的数据集，并将其边权统一赋为1进行实验。

　　我们使用了如下数据对两个算法进行了比较：

　　表1实验数据集规模及其描述

　　[数据集名称＼&顶点数＼&边数＼&应用领域＼&ZacharyKarateclub＼&34＼&78＼&社会网络＼&Geom＼&7343＼&11898＼&生物信息＼&KDDcitation＼&27770＼&352807＼&社会网络＼&]

　　注：该文所做的实验都是在一台CPU为奔腾M2.4G，内存为512M的电脑上完成的。软件平台为：WindowsXPSP2，MicrosoftVisualStudio6.0。

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。