节点间依赖度的社团结构划分.docx

节点间依赖度的社团结构划分《物理学报》2014年第十二期1方法的描述1.1主要思想在大量的实验和观察中发现在划分社团结构的过程中一个节点的划分往往依赖于和它有最多公共邻居的邻居节点或者依赖于它的大多数邻居节点的划分.1.2基本概念1)节点对节点的依赖度节点a对它的邻居点b的依赖度Dab定义为其中nab表示节点a和节点b的共同邻居的数目ka表示节点a的度.称节点a为起始节点节点b为终止节点.2)节点对社团的依赖度节点a对社团C的依赖度DaC定义为其中naC表示社团C中节点a的邻居的数目.3)依赖节点如果节点b是节点a的一个邻居节点并且节点a对节点b的依赖度不小于节点a对它的其他邻居节点的依赖度则称节点b是节点a的一个依赖节点称a对b的依赖度为节点a的最大依赖度.4)节点对社团的条件依赖度节点a对社团C的条件依赖度DamC定义为5)社团的公共节点如果一个节点对几个社团有着相同的依赖度和条件依赖度那么称这个节点是这几个社团的公共节点.1.3实现步骤以下结合对著名的Zachary空手道俱乐部人际关系网络[29](图3显示了该网络的原始状态)的社团划分过程来说明本文的社团划分方法.1)去除复杂网络中度为1的节点并将它们邻居的度减1直到该复杂网络中不再存在度为1的节点.在复杂网络中划分社团结构时度为1的节点必然和它的惟一邻居归于同一社团而它的存在对它的邻居的归属没有任何影响因此在划分社团之前可先将这类节点去除.在空手道俱乐部网络中去掉度为1的节点12并将节点1的度减1。2)计算复杂网络中所有节点的最大依赖度并在这些最大依赖度中找到最大值Dm.找到这个最大值Dm所对应的所有起始节点(这些节点须具有惟一的依赖节点)将它们分别和各自的依赖节点组成小的社团.这些依赖节点称为社团的初始节点.表1给出了空手道俱乐部网络中各节点的最大依赖度在本步中Dm的值为1表2显示了这本步得到的2个社团.3)对于社团的初始节点或者未划分到社团的节点s如果s对现存的某个社团的依赖度大于0.5则将节点s吸收进这个社团;如果节点s对它的邻居的最大依赖度不小于上步中的Dm且s对于某个社团的条件依赖度大于0.5则将节点s吸收进这个社团.如果节点s是某个社团的初始节点则将节点s所在社团中的所有节点吸收进这个社团中.表3显示了经过本步骤得到的社团的结果13和27两个节点对两个社团的依赖度分别大于0.5被吸收进对应社团.4)重复步骤3)直到没有节点被吸收进社团.此时从未划分到社团的节点和社团的初始节点的依赖度中找到最大值将对应于该最大依赖度的具有惟一依赖节点的起始节点s吸收进社团(如果终止节点属于这个社团)或者将节点s和终止节点组成一个小的社团(终止节点不在一个社团中).在对空手道俱乐部网络的划分中本步骤的最大依赖度为0.917对应于节点33对节点34的依赖度将节点33吸收进社团2.5)重复步骤4)直到没有节点被吸收进社团并且没有新的社团成立.6)此时社团外的节点与它们的邻居关系不够紧密或者具有一定的歧义性.在空手道俱乐部网络中此时社团外的节点为671017.计算社团外节点对现存社团的依赖度和条件依赖度并从这些依赖度和条件依赖度中找到最大值将对应的节点(这些节点须具有对应于该最大值的惟一的社团)吸收进相应的社团中.如果有节点满足步骤3)的条件则执行步骤3).直到没有节点被吸收进社团为止.表4显示了本步骤后空手道俱乐部社团的结果.7)对于现存的社团如果社团规模过小(例如社团中节点数目少于网络中节点总数目的5%)则将该社团中的节点依照上述步骤重新划分入现存的满足条件的其他社团.在对空手道俱乐部网络的划分过程中没有出现规模过小的社团.8)对于未划分到社团的节点根据步骤5)可知它们满足公共节点的定义属于与它们相连的社团的公共节点.在空手道俱乐部网络中节点10作为社团1和社团2的公共节点而存在.重新计算所有节点对现存社团的依赖度和条件依赖度确保所有节点对它所处的社团的依赖度大于对其他社团的依赖度或者在依赖度相等的情况下有最大的条件依赖度否则将不满足条件的节点以及受它归属影响的节点重新划分到合适的社团.经过以上步骤再将步骤1)中的度为1的节点划归它们邻居所在的社团中即可得到该复杂网络的一种社团划分.对空手道俱乐部网络度为1的节点12属于社团1其他节点的划分与表4保持一致节点10是两个社团的公共节点.1.4复杂度分析对于一个包含n个节点和m条边的复杂网络本文算法在实现过程中步骤1)所需的时间复杂度为O(n).步骤2)计算节点的最大依赖度所需的时间复杂度为O(mn)为便于步骤2)和步骤4)从大到小取用将网络中所有节点的最大依赖度排序所需时间复杂度为O(nlog2n).将一个度为k的节点吸收进社团最多需要计算k次节点对社