一种新的社团挖掘算法MFA(2)

　　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快速算法的结果