摘要：介绍了一种新的社团挖掘算法MFA(MaximumweightededgeFirstAlgorithm)，该算法是一个优先考虑边权值进行社团划分的算法，同时也继承了通过优化Q值进行社团划分的算法的优点。通过实验证明，该算法完全正确的将加权的Zachary网络划分为个数分别为16和18的两个社团，要远优于其他大部分社团划分算法。
关键词：社团挖掘;算法;MFA 论文多少钱
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。
算法执行速度如下：
表2算法运行时间比较(单位：毫秒)
[\&Zachary\&Geom\&KDD\&加权Newman算法\&15\&10531\&938250\&MFA算法\&16\&11352\&956737\&]
可见两者的运行时间相差无几，另外由上述的时间复杂度分析也可以看到，MFA算法在时间复杂度上并没有质的提高，这一点在实验中得到了证实。
算法的执行效果比较如下：(在这里我们直接比较Q值)
表3算法的模块Q值对比表
[\&Zachary\&Geom\&KDD\&加权Newman算法\&0.371795\&0.776724\&0.506033\&MFA算法\&0.434521\&0.804435\&0.547832\&]
从上表可以看出，MFA算法在效果上已经超越加权Newman快速算法。而且，对于小数据集的详细分析也证实了MFA法准确性的大大提高，以下两图所示的就是加权Newman快速算法和MFA算法对Zachary网络进行分析得到的详细结果。
图2加权Newman快速算法的结果
图3MFA算法的结果
仔细分析两图可以发现，加权Newman快速算法对于Zachary网络的划分，依然存在着10这个错误划分的节点，而在MFA算法中，所有的节点都能够被正确的划分到相应的社团中去，得到与实际结果完全相符的分别拥有16和18个顶点的两个社团。
4结论
MFA算法与加权NEW快速算法相比，已经有了比较大的进步，但是它仍然存在许多可以改进的地方。例如是否可以用CNM算法的思想进一步提高查找和合并的效率?较高的模块Q值在大数据集中的可信度又有多高?这些都是值得进一步深入探讨和研究的问题。总体来说，MFA算法的表现已经相当好，在模块Q值和准确性方面可以说是目前最好的算法之一。
参考文献：
[1]王艳，李应兴，靳二辉.复杂网络健壮社团挖掘算法[J].计算机工程与应用，2012，31(6)：40-43.
[2]李翔，李仕强，赵青虎.基于边聚类方法的复杂网络社团挖掘研究[J].电脑知识与技术，2012(10)：11-13.
[3]杨博，刘大有，金弟，等.复杂网络聚类方法[J].软件学报，2009(1)：58-70.
[4]周斌，程慧，杨立志，等.基于贪婪算法的符号网络中社团结构快速发现算法[J].大众科技，2009(12)：52-53.
转载请注明来自：http://www.lunwencheng.com/lunwen/dzi/7486.html
