探究超级网络的具体算法

1。算法研究

GN算法可以称得上是一种较为经典的社团区划算法，其与模块度搭配后更是常常能够取得较为良好的区划结果，而且GN算法的限制条件较少，适应性较高，其应用面也较为广泛。但近期通过研究我们发现该算法在区划准确性方面仍存在一些不足，GN算法对于与相连各社团连边均等的点的划分归类存在不足，常常出现错误，划分结果不够理想，例如在对Zachary空手道俱乐部网络进行划分时，节点3的错误划分。Zachary空手道俱乐部网络是复杂网络与社会网分析领域中常用的一个经典测试网络，WayneZachary用几年时间观察一所大学空手道俱乐部成员间的社会关系,并构造出俱乐部成员的社会关系网，网络包含34个节点，每个节点表示一个俱乐部成员,节点间的连边表示两个成员之间的朋友关系。调查过程中,该俱乐部因为主管与教练之间的争执而分裂成两个以他们二人为核心的小社团。该网络作为一个真实的社会关系网,常常被用于测试社团区划方法的准确性与有效性。

2。GN算法对Zachary空手道俱乐部网络进行划分的结果

GN算法虽然非常经典，但其对均等节点的划分常常存在问题，划分效果不够理想，本文提出的新算法在GN算法的基础上引入标准化程度中心性理论方法，该方法可以用于衡量某一节点在某团体内的相对重要程度，可以有效地对均等节点等歧义节点进行度量与测算，从而能够有效地弥补GN算法在均等节点划分上的不足。另外，当前传统GN算法对划分对象的处理基本都是基于单网络视角的，这样就未能将社团区划前后的节点拓扑属性进行比对，也就未能从此角度对社团的区划进行审视与改进。新算法引入超网络理论方法作为算法的主要框架，将划分前的整个网络视为全网络，而将划分之后的各个社团网络视为子网络，进而建立起超网络理论分析的模型架构，将超网络的相关理论方法运用其中，可以有效地弥补GN算法在社团划分前后节点拓扑属性比对方面的不足。程度中心性算法是当前测度网络节点重要程度的一种主要方法。拥有较高程度中心性的个体，在这个团体或网络中也具有一个较为重要的地位。其公式如下，公式(1)为绝对数值，就是把某个体的关系数加总，公式(2)为标准化数值，是将其除以该个体在该网络中最大可能的关系数，便于不同网络间的比较。

3。具体操作

直到每个节点就是一个退化的社团为止。然后选择具有模块度Q局域峰值的社团区划结果进行分析。分析选定结果中社团间连边的顶点Qv是否符合其与各相连社团的连边均等，我们将与相连各社团连边均等的节点定义为均等节点jdv，即判断此时QjdvV是否成立。则比较其全网标准化程度中心性1SQDQSdvSCvg和其在所属社团内的子网标准化程度中心性1ZaZaGQaDQGdvZCvg（设此时QZavG），若其全网标准化程度中心性大于其在所属社团内的子网标准化程度中心性，即DQaDQSCvZCv，否则结束。计算网络中经过每条边的最短路径数目B(e)，ijijvvVBene，ijne表示节点,ijvvV间最短路径中包括边e的数量。找到经过最短路径数目最多的边并将它从网络中移除，并将移除边的顶点按照其对应模块度Q值的不同分别记录下来，即按照模块度值的不同生成对应的社团间边顶点的集合QV。该点复制至选定区划结果的其他社团中，再计算其在新的社团内的子网标准化程度中心1ZxQZxQGvQxDQGvdvZCvg，（xa），将xDQZCv与其全网标准化程度中心性DQSCv进行比较，找到大于其全网标准化程度中心性且值最大的结果，则此时对应的区划结果即为所求。

作者：武澎 王恒山 刘奇 单位：上海理工大学