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

姓 名 论文（设计）题目 学 号 所在专业 计算机科学与技术专业 虚拟社群成员重要性评价算法的实现 选题的目的和意义： 互联网技术的发展同时使得人与人之间知识和情感的来源和表现形式更加多样化。电脑的使用者通过网络技术架构了一个个社会关系网络，这个完全通过互联网所构建的社会网络是虚拟社群的重要基础。虚拟社群中的社会网络与真实社区中的一样，也存在人际关系中的强联系和弱联系等人际网络关系特性，从而能够在虚拟社群中提供信息交换、知识共享和社会支持。社群成员通过社区的互动，可以建立各种各样的关系。 然而，虚拟社群中的协作与交流又受着各种因素的影响，如社群成员的参与动机、满意度、互动度等。这些因素决定了对于一个社群，不同的社群成员重要性是不同的，现在已经有几种不同的社群成员重要度评价模型和算法，如基于page rank 思想、基于中心性指标集、基于效率矩阵思想等等，本题将从算法复杂度、时空开销、结果准确度等等方面对这三个算法进行比较，来研究虚拟社群成员之间彼此的关系，描绘出虚拟社群网络结构及成员之间信息流动的情形，了解社群内不同个体之间关系的强度，探讨网络结构与社群成员的参与动机、社群满意度及忠诚度的关系，以期促进虚拟社群内的交流与关系的加强。 文献综述（国内外研究现状、研究方向、进展情况、存在问题等，并列出所查阅的主要国内外参考文献，要求3000字以上）： 一、“意见领袖”概念。 在群体中有一小部分人受到成员的敬重与信赖，互动参与程度高，对社群的贡献大，知名度相当高，他们经常引出新的论题，引导学习互动，具有较丰富的社交经验和专业知识，解决问题能力较强，具有强烈学习动机，乐于分享个人经验和心得，积极帮助其他成员学习知识，我们称其为“意见领袖”。他们在社群中发表文章、分享知识，受到了多数人的关注，是群体的核心人物，是社群中具有很强的凝聚力。如果一个群体中缺乏意见领袖时，社群图就会显得很散乱，网络结构关系就显得很松散。还有一部分成员处于社群的边缘，缺乏沟通和共享，说明他们与社群中的其他成员交流不积极，很少在社区发表文章和观点，对社群的贡献不大。 用社会网络理论来分析，网络中的每个结点都扮演着不同的角色。 意见领袖是在社会网络中占有核心位置的结点，他能够影响网络中的其他结点对事件的看法，社群则是有相互联系紧密的结点组成。那些贡献不大的成员处于网络的边缘位置，与其他结点交流不多。 二、三个算法简介。 1.基于中心性指标的社群成员重要性评价算法。 为了准确地评价成员在网络中的核心成员，引入以下的概念。 (1) 点度中心度 “点度中心度”(degree centrality)是一个最简单、最直观的指标,它描述的是一个节点位于图中“核心”位置的程度，刻画了该点与图中其他点发展交往关系的能力。点度中心度分为绝对点度中心度和相对点度中心度，点ni绝对点度中心度(用自CADi表示)就是该点的度数，即： CADi = d(ni) xx大学本科毕业论文（设计）开题报告

点ni相对点度中心度(用CRDi表示)定义为该点的度数与其最大可能的度数之比，即： CRDi?d(ni) n?1其中n为图中的节点数。 在社会网络中，如果一个节点的点度中心度很高，说明这个点很可能是该网络的核心，该点与其它点的交往是比较频繁的。如图1所示，为一个具有8个节点的社会网络。 图1 8个节点的社会网络 图中各个节点的绝对点度中心度和相对点度中心度如表1所示。 表1 各个节点的绝对中心度和相对中心度 绝对点度中心度 相对点度中心度 A 1 0.143 B 1 0.143 C 5 0.714 D 2 0.286 E 3 0.429 F 3 0.429 G 2 0.286 H 3 0.429 (2) 中间中心度 “中间中心度”(betweenness centrality)描述的是一个节点起到“中介”（或者“桥梁”）作用的程度，它刻画了该点控制图中其他点之间交往关系的能力。 中间中心度分为绝对中间中心度和相对中间中心度。假设图中点nj和nk之间存在的测地线数目用gjx来表示，第三点ni控制这两点交往的能力用bjk(i)来表示，定义为该点处于点nj和nk之间测地线上的概率，点nj和nk之间存在的经过点ni测地线数目用gjx(i)来表示，则： xx大学本科毕业论文（设计）开题报告

bjk(i)?gjk(i)gjk 点ni的绝对中间中心度（记为CABi）定义为将该点对于图中所有点对的控制能力加起来，即： CABi??j?kbjk(i),j?k?i且j?k 点ni的相对中间中心度(记为CRBi）是其绝对中间中心度的标准化形式，为该点的实际绝对中间中心度与其最大可能的绝对中间中心度之比，定义为： nnCRBi?2CABi?2n?3n?22?j?kbjk(i)n?3n?22nn 在社会网络中，中间中心度反映了节点控制其它点之间交往关系的能力。如果有很多节点之间的最短路径通过这个节点，说明这个节点是很重要的,是连接网络中其它节点的重要“环节”之一。图1所示图的各个节点的中间中心度和相对中间中心度如表2所示。 表2 各个节点的中间中心度和相对中间中心度 绝对中间中心度 相对中间中心度 A 0 0.000 B 0 0.000 C 13 0.265 (3) 接近中心度 “接近中心度”(closeness centrality)描述的是一个点与图中其他所有点之间距离的远近，如果该点与图中其他所有点之间的距离都很短，则说明该点与图中其他所有点都很“接近”，也就是说该点的接近中心度很高。接近中心度刻画了一个点摆脱图中其他点控制的能力，如果网络中的一个行动者在与其他行动者的交往过程中较少依赖于其他行动者，则此行动者拥有较高的接近中心度。 接近中心度分为绝对接近中心度和相对接近中心度，点ni的绝对接近中心度（记为CACi）就是该点与图中其他所有点的距离之和，即： D 3 0.061 E 4 0.081 F 4 0.081 G 1 0.020 H 1 0.020 CACi??j?1d(i,j) 其中d(i,j)力表示点ni和nj之间的距离。 点ni的相对接近中心度(记为CRCi)是其绝对接近中心度的标准化形式，为该点的实际绝对接近中心度与其最大可能的绝对接近中心度之比。经证明，相对接近中心度为： nCRCi常用相对接近中心度来进行计算。 CACi??2(n?1)?nj?1d(i,j)2(n?1) xx大学本科毕业论文（设计）开题报告

在社会网络中，接近中心度反映了节点到达其它节点距离的远近。其值越小，说明该点与其它节点就越接近。图1所示图的各个节点的接近中心度和相对接近中心度如表3所示。 表3 各个节点的接近中心度和相对接近中心度 绝对接近中心度 相对接近中心度 A 15 0.306 B 15 0.306 C 9 0.184 D 12 0.245 E 11 0.224 F 11 0.224 G 14 0.286 H 13 0.265 (4) 基于中心性指标的社群核心成员挖掘模型 挖掘网络社群的核心成员是一个有意义的问题。四川大学的唐常杰教授在该方面作了一定的探索，可用于社会网络社群的核心挖掘。 设G?(V,E)是传统意义上的图，F是其节点集合，E是图G边的集合，K是一个结点。 A. Cd(K)为节点K的相对点度中心度，其中n是一个网络的结点数，a(i,k)是一个二值变量，为1说明结点i，k之间直接相连，为0说明不直接相连。 Cd(K)??a(i,k)i?1nn?1 B. Cb(K)是节点K的相对中间中心度，其中n是一个网络的结点数，gij(k)是一个二值变量，表示结点之i，k之间的最短路径是否通过结点k，通过k则为1，否则为0。 ??gCb(K)?ijnnij(k) (n?1)2C. Cc(K)是节点K的相对接近中心度，其中l(i,k)为结点i，k之间的最短路径长度。 Cc(K)??l(i,k)i?1n(n?1)2 D. 向量(Cd(K),Cb(K),Cc(K))称为节点人的中心度。 直观地来看，点度中心度反映了节点在网络中的活跃程度。一个结点的点度中心度很高意味着它很可能是网络的核心。中间中心度衡量的是某个特殊的结点位于其它结点间的程度。接近中心度衡量了一个结点和其它结点间距离的远近，反映了一个结点到达其他所有结点的速度。而中心度集成了上述三者，描述了节点K在网络中的中心地位的程度。图1所示的各个节点的中心度向量如表4所示。