复杂网络基础7

复杂网络复杂网络中的挖掘复杂网络中的挖掘7.1引言7.2重要节点挖掘研究现状及评价指标7.3常见重要节点挖掘方法7.4社团结构挖掘研究现状及评价指标7.5常见社团挖掘方法7.1引言在复杂网络的研究中，通常只关注哪些节点有边相连，至于节点在什么位置、边是什么形状都不是关注的重点。通常把不依赖于节点的具体位置和边的具体形态所表现出来的网络结构叫网络拓扑。复杂网络本质上都是非同质拓扑结构，该种结构也决定了网络中每个节点的重要程度是不同的。在复杂网络的挖掘研究中，对网络中节点的重要性进行评估，发掘网络中的重要节点具有重要的实用价值。尤其是对各种各样具体的实际网络，更能针对性地分析网络性质制定正确的策略和措施。7.1引言1）在犯罪关系网络中，可以迅速定位犯罪团伙的头目，集中警力进行布控；2）在搜索引擎的应用方面，可以把搜索到的正确结果根据其匹配和重要程度排序后返回用户；3）在谣言传播网络中，可以发掘出谣言来源，避免出现“蝴蝶效应”；4）在大规模计算机网络总，可以根据服务器节点的重要程度进行有针对性的备份，从而在保证网络鲁棒性的同时，由能有效地节省资源。5）在传染病或者病毒网络中，可以针对性地先治疗或者隔离病源，有效防止病毒的传播和扩散。7.1引言复杂网络通常会存在不同的社团，社团内部节点间的连接相对紧密，而社团间的节点只有少量连接。图7.1是一个小型具有社团结构性质的网络，该网络中包含了三个社团。在不同的实际网络中，社团结构的实际意义通常会有所不同，对社团结构的研究是了解整个网络结构和功能的重要途径，因此社团结构在实际网络中有着重要意义。7.2重要节点挖掘研究现状及评价指标不同领域的复杂网络研究侧重点有所差异，因而重要节点挖掘算法优劣的评估指标也不同。7.2.1介绍重要节点挖掘研究现状；7.2.2分别介绍社会网络分析和系统科学分析中的算法优劣评价指标;7.2.3介绍合理评价指标应当满足的几个条件。7.2.1重要节点挖掘研究现状评价网络中节点重要性的方法有很多，但其本质均是源于图论以及基于图的数据挖掘，对应于图论中的最关键节点问题（mostvitalnodeproblem）和最关键边问题（mostvitaledgeproblem）。复杂网络的节点重要性研究最早开始于社会网络分析领域，并且至今仍是学术界的研究重点。随着复杂网络研究的不断深入，系统科学研究领域、信息搜索领域等众多领域均分别独立地提出了类似的问题。7.2.1重要节点挖掘研究现状社会网络分析认为节点的重要性等价于该节点与其他节点的连接而使其具有的显著性，其特点在于不破坏网络的连通性，且仅考虑单个节点的重要性而不考虑节点集的重要性。系统科学的分析方法是通过度量节点删除对网络连通性的破坏程度来反映复杂网络中节点（集）的重要性，即“破坏性等价于重要性”。在互联网搜索领域，计算机科学家也提出了很多算法来判断网页节点的重要程度。多指标体系的综合评价方法也可以用于网络中节点重要度的评价，7.2.2重要节点指标分析1．不破坏网络结构的指标该类指标以不破坏网络的整体性的前提下，通过“放大”节点的某些属性的显著性差异从而评估节点的重要性程度。在已提出的指标中主要包含中心性和声望两大类。中心性的概念最早来源于应用统计学的思想，仅用于估计样本点的集中程度。这类指标将节点的某个属性定义为中心化指标，通过比较网络中所有节点的该种属性，找出对网络的拓扑结构起着较高作用的重要节点。声望是另一类用于评估节点重要程度的评估指标。该类指标认为网络中的每个节点都有一个声望值，当某个节点与较多的节点有联系或者与它连接的节点本身具有较小的声望，认为该节点是这个网络中比较“著名”的节点，则该节点是网络中的最重要节点。7.2.2重要节点指标分析2．基于节点删除方法的指标该类指标利用网络的连通性来反映系统某种功能的完整性，通过度量节点对网络通性的破坏程度来反映网络节点的重要性。一般来讲，系统中节点的删除除了对系统通性可能具有破坏，还会影响到系统的一些其他指标，所以通过计算这些指标的性能化也能度量节点的重要性。最大连通分支尺寸：R＝NR／N平均最短路径长度：网络效率：网络生成树数目：τ（G）＝det（AAT）()21NijijLdNN=-å()211NCijijLNNd=-å7.2.3合理评价指标所需条件（1）中心化指标应该是对称的，若对网络的节点重新编号，中心化指标应该不改变。（2）无论将一个节点看成整个图的节点，还是将其看成一个连通分支的节点，所得到的中心化指标的值应该一致。（3）孤立节点的中心化指标应该最小。（4）在具有链式结构的网络中，节点的中心化指标应该从边缘向中心递增，即越靠近中心，节点的中心化程度应该越高。（5）在所有的具有N个节点的连通网络中，链式结构网络的顶端节点的中心化指标应该最小，而星型结构网络的中心节点的中心化指标应该最大。（6）移去某个节点的某条边，至少不会增加该节点的中心化指标。7.3常见重要节点挖掘方法常见的节点重要性评估方法有很多种，根据评估方法侧重点的不同，可以分为三类：基于节点之间的直接连接状态、基于目标节点到其他节点的最优连接方式以及基于模拟流的分析。7.3.1基于节点关联性的方法7.3.2基于最短路径的方法7.3.3基于模拟流的方法7.3.4其他分析方法7.3.1基于节点关联性的方法1．节点度设网络具有N个节点，则节点vi的度指标定义为：归一化的度指标定义为：CD（vi）＝Cd（ki）／（N－1）2．子图计算节点vi的子图中心性公式为：µn（vi）＝（An）iiCd（vi）＝ki()()0vv!kisinCnm¥==å子图例子根据节点所在回路的不同（不考虑五边形、六边形、七边形、八边形）可以将它们分为三类：（1）节点v1、v2、v8存在于一个三角形回路中；（2）节点v3、v5、v7分别存在于两个四边形回路中；（3）而节点v4、v6存在于三个四边形回路中。实际计算结果是，节点v1、v2、v8具有最高的重要性，节点v3、v5、v7具有最低的重要性，原因是三角形的权重大。7.3.2基于最短路径的方法1．介数节点vi的介数可以表示：该指标可归一化定义为：CB（vi）＝Cb（vi）／［（N－1）（N－2）／2］2．特征向量()()vststbistgiCn=å()-11vNeiijjjCλae==å7.3.2基于最短路径的方法3．近似特征向量指标则CA（vi）＝CD（vi）为最终的近似特征向量指标对于加权网络有：4．接近度归一化的接近度指标定义为：Cc（vi）＝（N－1）Cc（vi）111vvv,0,1,2,...,innininjjUjCCCnD1111vvvv,0,1,2,...,innijinjninjjUjCCCCnD()11vNciijjCd-=轾犏=犏臌å7.3.2基于最短路径的方法【例7.1】图7.4是一个具有13个节点、18条边的测试网络，请分别用特征向量指标Ce、近似特征向量指标CA、接近度指标CC分析网络中各节点的重要性。7.3.2基于最短路径的方法解：分别运用公式（7.13）、（7.14）和（7.17）可得：节点v1v2v3v4v5v6v7v8v9v10v11v12v13Ce0.200.280.280.320.330.320.280.280.200.320.280.280.20CA0.0550.0790.0790.0890.0940.0890.0790.0790.0550.0890.0790.0790.055CC0.260.320.320.410.500.410.320.320.260.410.320.320.417.3.2基于最短路径的方法5．节点删除法TLOS（vi）=DLOS（vi）+ILOS（vi）其中直接网络效率损失为：间接网络效率损失为：网络总损失为：1,1DLOSvNijjiijd1,1,v,vILOSvNNljillijljiljd11v,vTLOSvNNljiijlljd7.3.3基于模拟流的方法1．流介数2．近似流介数()()vjkFijkjkgiCg=å1(v)(),jnjnmUCmCmmi1vv(v)iDFMijkjnjUCC7.3.3基于模拟流的方法【例7.2】图7.5是一个有13个节点、18条边的测试网络，请分别用流介数和近似流介数指标分析网络中各节点的重要性。7.3.3基于模拟流的方法解：7.3.4其他分析方法1．累计提名2．信息指标1nniijjjninnkkjjkjqaqqqaqvlimnCNiinCNq11viiijjCNq1vIiijjiCqN7.3.4其他分析方法【例7.3】分别用节点删除法、累计提名和信息指标分析40个艾滋病患者性关系网络（图7.8）中的每个节点的重要程度。214132539402719182024232221171516121097811431653826373635313234332930287.3.4其他分析方法解：(1)用节点删除法求得结果:（2）用累计提名所得结果：节点162611315228323828CR0.3710.2150.1910.1310.1250.1090.0840.0750.0750.069节点v20v14v36v29v2v9v34v23v19v12CR0.0560.0470.0430.0430.0410.0400.0310.0300.0300.030节点151721252718394034CR0.0300.0300.0300.0280.0250.0240.0240.0240.0240.024节点63713243373011035CR0.0240.0240.0240.0230.0230.0230.0200.0200.0190.019节点16221120261412151721CCN21.6212.5110.059.3668.9007.7326.9366.9366.9366.936节点528192382531381827CCN5.5924.8814.5704.4754.1214.0143.9003.5953.0042.855节点132323462992436CCN2.4802.0001.8641.7941.7941.7941.7451.4741.4351.395节点739403433130103735CCN1.3221.1531.1530.9950.9170.6410.5600.4730.4470.3197.3.4其他分析方法（3）第一种信息指标所得结果：（3）第二种信息指标获得结果：节点16222620112819311412Ci04170.3920.3880.3570.3510.3480.3360.3100.3030.299节点151721382325275818Ci0.2990.2990.2990.2920.2900.2850.2830.2820.2740.266节点29323613394024234Ci0.2650.2480.2420.2360.2280.2280.2270.2250.2220.222节点6973433303711035Ci0.2220.2200.2180.2170.2160.2120.1970.1850.1820.180节点1626222028111931538CI0.5160.4720.4660.4250.4180.4060.3940.3720.3600.346节点1432121517218232725CI0.3450.3320.3290.3290.3290.3290.3270.3270.3120.311节点2934183336291334CI0.3050.2980.2920.