教事技本与率用
算法分析
基于加权的社会网络重要节点发现算法研究
邓传军
(江西工业工程职业技术学院江西萍乡337055)
摘要:本丈针对网络一般算法存在问题,提出来一种基于加权的社会网络重要节点发现算法。该算法基于社会网络中节点和边的属性进行有向加权社会网络建模,融含节点之间相对重要性理论和网络拓扑原理,共同发现加权的社会网络中的重要节点。
关键词加权节点算法
中图分类号:TP39 1概述
文献标识码：A
文章编号:1007-9416(2014)08-0133-02
只需将R与T都设置为V，即R=T=V。
不管是社会网络，还是WWW网络，一般介绍的各种算法几乎都是站在整体的角度，或显式或隐式地对网络中所有节点的重要性进行全局的排序，很少有学者关注网络中节点的相对重要性。然而，在数学领域著名的“六度分割理论形象地损示了客观世界存在普遵的联系性。在客观世界中，任何两个个体之间哪怕是看起来毫不相干的两者之间都是存在着各种潜在的关系。在对网络节点重要性的研究方面， 2000年Chang，Cohn和McCallum提出一种主体敏感性的HITS算法变种，之后人们受到他们的启发提出了基于PageRank算法的个人主体敏感变种算法，虽然这些研究是主要是基于搜索引擎对搜索结果的优化，要达到搜索内容个人主体化的目标，但是他们的算法已经为人们开启了对网络节点相对重要性研究的思想大门。
在研究了ScottWhite与Padhraic Smyth总结的相对重要性发现框架基础上，我们对其中四种渐进间题的定义做了扩展，让该框架不仅适用于加权网络，让其对有向网络也给予支持。下面给出我们对网络节点相对重要性的定义，
定义1：给出图G(V,E),根节点r和节点t,其中(r,t)G,我们定义非负值I(tr)为节点t对于根节点的相对重要性
定义2：给出图G(V,E),将T(G)中的节点相对于根节点r的重要度进行排序,I(Ir),其中T=V，为了到达这一目的，我们先针对每个teT计算()值，然后将值进行排序，其中t)值越大，则说明相对重要性越强。
定义3：给出图G(V,E)，一个待排序的节点集合T(G)与一个根节点集合R(G),其中R=V，计算所有集合T中的节点对集合R的相对重要性，即I(TIR)
这里与定义2中一样，要计算I(TR),其中reR，通常我们需要先分别计算(tr),IeR)。比如，我们可以用平均对集合R的相对重要性来定义I(tR)：
1()
(
RI
(1
如果不用平均值的话，我们也可以这样定义I(tR)=min(I(tr)： reRJ.
定义4：给出图G(V，E)，要求出说有节点的相对重要程度，我们
图1简单有向图
收稿日期：201408-16
从上述对四种渐进问题的定义，我们不难看出该定义具有较强的适用性，不仅可以将该思想应用于大型网络的小社区重要节点发
现，面且可以进行全局重要节点挖掘。 2对网络节点权值的定义
对于双加权社会网络中节点权重的定义间题，国内外学者们都曾从不同的角度给出很多种不同的定义，在本文中，我们主要考虑的是社会网络，因此我需要更多的考患是节点(大多时候是用户或个体)，在网络中的声望或者活跃情况，而社会网络中某个节点越是活跃，他越是能够带动影响越多的节点，一起参与到网络交互当中，故此我们可以用一个节点的活跃度来作为社会网络节点的权值大小指标。活跃度在社会网络中的表现形式可以是打电话、发信息，聊天、聚餐、郊游等等，只要是发生在网络中某个节点上的事件。我们都可以视为是该节点活跃度的一个展现方面，将这些事件进行网络全局的归一处理，即可得到我们在要的加权社会网络节点的权值，结合上文所阐述的内容，我们给出网络节点权值的一般股定义，设网络个体提交发布的总消息或资源等交互总数为M，使用该在线社交网络平台的时长为T(天)。则在网络中该个体的活跃度可以被定义为a，=M，/T。
然而，虽然上述定义能够在一定程度上，描述该网络个体的活跃情况，但是，在在线社交网络中，很有可能会出现用户注册时闻很短，却在短时间内大量的进行网络交互行为，然面，往往绝大多数用户是保持在一个较低的活跃度水平上的，由此可见该定义所描绘的活跃度，并不能更好的展现一个节点的真实活跃情况，
针对上述原因，我们提出一种新的加权网络节点权值定义方法，定义如公式2所示。
4, = 2-
(2)
其中M为在近某一个标准时间段T内，网络个体所发出的所有交互总数，为个体活跃度的调节因子。之所以如此定义，原因上文虽然提到一部分，然面，其主要原因是因为在实际处理真实网络数据集时，我们遇到很多异常个体，为了让所有网络个体都能够有个展现其活跃情况的刻画指标，面且该活跃指标又不能因个体的差异产生较大的起伏，因此结合了数理归一相关理论知识，我们将时间的概念弱化，采用统一时间段，这样较少了变量，让活跃度体现的就是该个体的真实活跃情况，并且通过调节因子，让节点活跃度始终保持在大约0小于1的区间之内，从而为下一步有向加权社会网络的重要节点发现提供了坚实的理论基础。
3基于加权的社会网络重要节点发现算法
在该算法中，针对任一有向图如图1所示，我们将相连的两节点
.下转第135页
作者简介：邓传军(1974一),男,江西吉安人,制教投,大学本科,工学项士,2005年毕业于履门大学计算机应用技术专业,从事计算机教学工作。
133