network --

jay d8251496b1 非法字符判断 4 years ago
src d8251496b1 非法字符判断 4 years ago
LICENSE 1db6da6fcf initial commit 4 years ago
README.md de66adff07 readme 4 years ago
pom.xml 133a9cb5d0 算法实现 4 years ago

README.md

评估节点重要性排序算法的快速方法

在研究复杂网络节点重要性的问题中,鲁棒性R是评价“重要性排序算法”的重要指标,它定义为σ-p曲线的面积:定义p为移除节点的比例,σ为删除比例为p的节点之后剩余网络中最大联通集团的规模(用比例表示):以p为横坐标,σ为纵坐标,就可以得到σ-p曲线。如下图 σ-p曲线

R的计算公式可表示为

: 此处输入图片的描述

其中,表示:删除比例为的节点之后剩余网络的最大联通集团的规模。计算R的关键在于计算出每一个p对应的σ。

最直观的方法,当然是删除比例为p的节点之后,利用广度优先搜索算法找到剩余网络中的最大联通集团;然而当网络非常大的时候,要想取得比较精准的R(需要p的间隔取值比较小),这种方法就会非常耗时!

我们这里分享一种快速的方法!

【正文开始】 该算法的核心思想:不是从原网络中逐渐地删点减边,而是在空网络中逐渐地添点加边。 事实上,并不会真的加边,简单描述如下:

  • 给定原网络G,并指定节点的顺序,假如是v1,v2,v3,……,vn,每个节点当前都不属于任何集团。
  • 将这些节点依次加入到空网络G’中: a)新加入一个节点vi,根据G记录的连边关系检查G’中是否有vi的邻居:

    • 若有一个邻居,将vi加入到邻居所在的集团中

    • 若有多个邻居,将所有邻居所在的集团进行合并

    • 若没有邻居,则vi自己成为一个社团,分配给它一个新的社团ID

算法描述如下:

Step1   读入网络G

Step2   读入节点的顺序,重要性较低的节点排在前面,记录为向量V

Step3   初始化一个空的映射向量NodeCluster,用以记录每一个节点所属集团的ID;
初始化一个空的映射向量ClusterNodes,用以记录每一个集团的成员节点。

Step4  for 节点vi in V :

4-1     记节点vi可能连接的集团的ID集合为Ci(初始化为空):
4-2     for 节点vj  in  vi的所有邻居(根据网络G访问):
            若vj存在于NodeCluster中(说明已属于某个集团):
则将vj所属的集团ID加入到Ci中。
4-3     若Ci为空   
            说明vi目前是孤立的,给它一个新的集团ID;
        否则
            记录Ci中编号最小的集团ID,记为minci ;
            将节点vi加入到编号为minci的集团中;
            将Ci中所有集团的成员节点都合并,均放入minci中;
            更新当前网络中的最大集团的编号。

Step5: 算法结束