xx大学本科毕业论文（设计）开题报告

表4社会网络中各节点中心度向量 A B C D E F G H Cd(K) 0.143 0.143 0.714 0.286 0.429 0.429 0.286 0.429 Cb(K) 0.000 0.000 0.265 0.061 0.081 0.081 0.020 0.020 Cc(K) 0.306 0.306 0.184 0.245 0.224 0.224 0.286 0.265 用来计算中心度向量的算法可以描述如下。 算法1计算节点中心度向量的算法 输入：社会网络图占厅 输出：每个节点的中心度向量 for each node i in SN { S[i].degree = computeDegree(i); shortpath[i][] = Dijikstra(i); } for each node i in SN { for each node j in SN for each node k in SN if i in shortpath(k,j) { //k!=i; S[i].betweenness += 1; } for each node j in SN S[i].closness += shortpath[i][j]; } return S[]; 2.基于Page Rank思想的社群成员重要程度评价模型 Internet网页之间的链接关系是一个典型社会网络，如何根据网页之间的链接关系找出高质量权威的网页提供给用户服务是搜索引擎所面临的一个重要课题。目前有大量的研究工作集中在这里，世界著名的搜索引擎Google所用的Page Rank算法可以根据页面的链接关系给网页评级，每个网页的得分代表了网页的质量和重要程度。与Web社会网络类似，在社交网络中，也具有相似的特点，一个社会成员在社会网络中的重要程度很大程度上取决于和他交流过的人的重要程度以及数量，具体表现为以下三 xx大学本科毕业论文（设计）开题报告

条性质： A.在Email社会网络中，如果有很多人和同一个人交流，那么这个人可能是很重要的； B.一个人虽然没有很多人和他对话，但是有重要的人和他进行交流，那么这个人也可能是很重要的； C.一个人的重要程度被平均的传递到他所交流过的人。 基于上述性质，引入以下定义： 社群成员的重要度描述社会网络中社群成员的重要程度，假设u是社群S的一个个体，Fu表示S中与u对话过的个体集合，v?S，Nv表示个体v向其它个体发出邮件的数量，R(u)表示个体u在社群中的重要程度： R(u)??R(v),v?Fu Nv如果用上述方法表示出社交社群的每个成员的重要程度，则这一组等式可以表示成一个方程组，对这个方程组进行求解，就可以得到每个社群成员的重要程度。例如，如图2所示，为一个具有3个成员的社会网络。 图2 三个成员的社会网络 应用定义来描述，则每个社会成员的重要程度可以表示为： R(A)?R(C) R(A) 2R(A)R(C)??R(B) 2R(B)?该方程组的一组特征解为(0.4,0.2,0.4)，其中A和C的重要度为0.4，B的重要度为0.2，表明在该社会网络中，A和C处于相对平等的重要程度，而B则处于相对次要的重要程度。 xx大学本科毕业论文（设计）开题报告

如上讨论，我们根据互联网上搜索引擎挖掘权威页面的方法，把社交社会网络社群成员重要程度的评价问题归结为一个方程组的特征解的求解问题。与互联网页的重要程度评价问题求解相比，一个社交社群网络的线性方程组规模比较小，通常为几十或几百，因而在特征解的求解上是比较容易的，在Google所用的Page Rank算法的论文中讨论了该方程组的数值解法。 3.基于效率矩阵的社群重要度评价算法 假设无向无权网络用图G?(V,M)表示。其中，图G中包含n个节点，V?{v1,v2,?,vn}m条边，表示图中节点的集合，M?{m1,m2,?,mm}?V?V表示图中边的集合。 定义1 节点度值 ki(i?n)是指节点vi与邻接节点的连接边的数量； 定义2 最有效路径lij(i?n,j?n)是指节点对(vi,vj)间传输信息或能量效率最高的路径；节点间的最有效路径是网络中信息传播的最直接、最有效的路径；在本文所研究的无权网络中，最有效路径等价于最短路径，即节点对之间所含边数最少的路径；相应路径上边的数量用来定义节点对之间的距离，用dij表示； 定义3 效率eij(i?n,j?n)是指节点vi至vj距离的倒数，即eij?1当i?j或节点对(vi,vj)不dij存在最短路径时eij?0；当节点对(vi,vj)互为邻接节点时，其传输效率值最大，即eij?1；当节点对(vi,vj)互不为邻接节点时，eij?(0,1)。节点间的传输效率表征了节点间相互作用的最直接、最有效的形式。由此，具有n个节点网络的全点对效率矩阵可表示为 ?e11?eE??21????en1e12e22?en2?e1n??e2n?? ?????enn?节点度是用于描述节点在网络中的直接影响力。一般认为，度值越大的节点在网络中起到的传输作用越大，其重要度就越高。但是，复杂网络是一个包含大量节点以及节点间存在复杂相互作用、依赖关系的统一整体，此时，虽然“桥连接”节点具有较小的度值，但其在网络中的受依赖程度却较明显，即网络节点对其的重要度贡献较大，相应的重要度较高，故仅依靠度值大小很难判断出节点的重要程度。实际上，如果存在非邻接节点之间的相互依赖程度显著高于邻接节点，那么非邻接节点之间的相互依赖就不容忽视。文献[5]提出一种基于效率矩阵的节点重要度评价算法，该方法综合考虑了网络节点的度值和整个网络节点之间的重要度贡献，利用最有效路径作为节点间重要度贡献的有效路由。节点的度值表征了节点的局部重要性，网络节点的重要度贡献体现了节点的全局重要性。 xx大学本科毕业论文（设计）开题报告

一般地，“桥连接”节点虽然具有较小的度值，但是其却处在网络中的“核心位置”，节点越处于“核心位置”，那么它和全网中的其它节点的相互作用程度就越大，即网络其他节点对其的重要度贡献越大，相应该节点的重要度越高，故可将节点的度值作为网络节点重要度评价的一个重要指标。为了更加准确地判定节点在整个网络中的全局重要性，文献[5]提出一种基于效率矩阵的节点重要度贡献计算方法。该方法弥补了重要性贡献矩阵法中节点重要度只依赖于邻接节点的不足。 一个节点的重要度大小依赖于网络其它节点对其的重要度贡献程度，节点之间的重要度贡献可以通过不同的路由传播，本文假设网络节点对待评估节点重要度贡献通过网络最有效路径完成，并且利用节点度值表征其对全网的节点的重要度贡献基准值。因此，网络中每个节点依赖于其余节点的程度可以通过效率矩阵计算 ?h1??e11?h??e2H????E?K??21????????hn???en1鉴于此，第i个节点vi在全网的相对重要程度为 e12e22?en2?e1n??k1??k??e2n???2? ?????????enn??kn?hj?j?1,j?i?hnij 式中，hij?eij?kj表示节点vj对节点vi的重要贡献。由上式可知，网络节点vj对节点vi的重要度贡献程度不仅和节点间的效率值eij大小有关，而且和节点vj的度值kj大小有关：如果eij越大，kj越大，则节点vj对节点vi的重要度贡献越大。 在考虑网络节点对待评估节点重要度贡献的基础上，结合待评估节点本身的局域重要性-度值，节点的重要度定义为 ?d1??k1??h1??d??k??h?D??2???2???2? ????????????????dn??kn??hn?由上可知，经过归一化处理后的第i个节点vi的重要度为 di??diki?(eijkj)?kj?in?dk?1n?(k?(ekk?1m?knn kmmk)