基于加权的社会网络重要节点发现算法研究

邓传军

摘要：本文针对网络一般算法存在问题，提出来一种基于加权的社会网络重要节点发现算法。该算法基于社会网络中节点和边的属性进行有向加权社会网络建模，融合节点之间相对重要性理论和网络拓扑原理，共同发现加权的社会网络中的重要节点。

关键词：加权 节点 算法

中图分类号：TP39 文献标识码：A 文章编号：1007-9416（2014）08-0133-02

1 概述

不管是社会网络，还是WWW网络，一般介绍的各种算法几乎都是站在整体的角度，或显式或隐式地对网络中所有节点的重要性进行全局的排序，很少有学者关注网络中节点的相对重要性。然而，在数学领域著名的“六度分割理论”形象地揭示了客观世界存在普遍的联系性。在客观世界中，任何两个个体之间哪怕是看起来毫不相干的两者之间都是存在着各种潜在的关系。在对网络节点重要性的研究方面，2000年Chang，Cohn和McCallum提出一种主体敏感性的HITS算法变种，之后人们受到他们的启发提出了基于PageRank算法的个人主体敏感变种算法，虽然这些研究是主要是基于搜索引擎对搜索结果的优化，要达到搜索内容个人主体化的目标，但是他们的算法已经为人们开启了对网络节点相对重要性研究的思想大门。

在研究了Scott White与Padhraic Smyth总结的相对重要性发现框架基础上，我们对其中四种渐进问题的定义做了扩展，让该框架不仅适用于加权网络，让其对有向网络也给予支持。下面给出我们对网络节点相对重要性的定义。

定义1：给出图G（V，E），根节点r和节点t，其中{r，t}G，我们定义非负值I（t|r）为节点t对于根节点r的相对重要性。

定义2：给出图G（V，E），将T（G）中的节点相对于根节点r的重要度进行排序，I（T|r），其中TV。为了到达这一目的，我们先针对每个tT计算I（t|r）值，然后将值进行排序，其中I（t|r）值越大，则说明相对重要性越强。

定义3：给出图G（V，E），一个待排序的节点集合T（G）与一个根节点集合R（G），其中RV，计算所有集合T中的节点对集合R的相对重要性，即I（T|R）。

这里与定义2中一样，要计算I（T|R），其中rR，通常我们需要先分别计算{I（t|r），rR}。比如，我们可以用平均对集合R的相对重要性来定义I（t|R）：

（1）

如果不用平均值的话，我们也可以这样定义I（t|R）=min{I（t|r）：rR}。

定义4：给出图G（V，E），要求出说有节点的相对重要程度，我们只需将R与T都设置为V，即R=T=V。

从上述对四种渐进问题的定义，我们不难看出该定义具有较强的适用性，不仅可以将该思想应用于大型网络的小社区重要节点发现，而且可以进行全局重要节点挖掘。

2 对网络节点权值的定义

对于双加权社会网络中节点权重的定义问题，国内外学者们都曾从不同的角度给出很多种不同的定义，在本文中，我们主要考虑的是社会网络，因此我需要更多的考虑是节点（大多时候是用户或个体），在网络中的声望或者活跃情况。而社会网络中某个节点越是活跃，他越是能够带动影响越多的节点，一起参与到网络交互当中，故此我们可以用一个节点的活跃度来作为社会网络节点的权值大小指标。活跃度在社会网络中的表现形式可以是打电话、发信息、聊天、聚餐、郊游等等，只要是发生在网络中某个节点上的事件。我们都可以视为是该节点活跃度的一个展现方面，将这些事件进行网络全局的归一处理，即可得到我们在要的加权社会网络节点的权值。结合上文所阐述的内容，我们给出网络节点权值的一般定义，设网络个体i提交发布的总消息或资源等交互总数为Mi，使用该在线社交网络平台的时长为Ti（天）。则在网络中该个体的活跃度可以被定义为。

然而，虽然上述定义能够在一定程度上，描述该网络个体的活跃情况，但是，在在线社交网络中，很有可能会出现用户注册时间很短，却在短时间内大量的进行网络交互行为，然而，往往绝大多数用户是保持在一个较低的活跃度水平上的，由此可见该定义所描绘的活跃度，并不能更好的展现一个节点的真实活跃情况。

针对上述原因，我们提出一种新的加权网络节点权值定义方法，定义如公式2所示。

（2）

其中为在近某一个标准时间段T内，网络个体i所发出的所有交互总数，为个体活跃度的调节因子。之所以如此定义，原因上文虽然提到一部分，然而，其主要原因是因为在实际处理真实网络数据集时，我们遇到很多异常个体，为了让所有网络个体都能够有个展现其活跃情况的刻画指标，而且该活跃指标又不能因个体的差异产生较大的起伏，因此结合了数理归一相关理论知识，我们将时间的概念弱化，采用统一时间段，这样较少了变量，让活跃度体现的就是该个体的真实活跃情况，并且通过调节因子，让节点活跃度始终保持在大约0小于1的区间之内，从而为下一步有向加权社会网络的重要节点发现提供了坚实的理论基础。

3 基于加权的社会网络重要节点发现算法

在该算法中，针对任一有向图如图1所示，我们将相连的两节点对节点之间的重要度定义，并且令；对于不相邻的任意两节点，如节点与节点，可以看出从到的路径集合包含{，，，}，将相邻的节点间相对重要度定义为两节点间的关系强度，这是因为关系强度是两个用户关注度和重要性的调和平均值，当两值相差较大的时候，调和平均值会比他们的算术平均值更接近较小的那个值。当节点对节点交互较少，而节点对节点交互较多时，那么会造成单向的高强度关系，采用调和平均值能够有效的避免这种情况的出现。另外，在的定义中采用所有用户的平均交互次数作为全局因子，这一措施可以有效的克服小社区的高局部强度效应。

4 结语

本文简单介绍了国内外学者提出的网络重要节点发现算法，对它们的优缺点进行了对比讨论分析。同时指出了这些算法对于发掘社会网络中重要节点的局限性。提出了新的基于加权的社会网络重要节点发现算法，新算法在双加权与有向的基础上，考虑节点与节点间紧密关系程度，节点个体的活跃度以及考虑了任意两节点间的相对重要性。根据新算法提出了评估重要节点的指标，并对算法中的公式进行详细的解释，针对算法中任意节点间相对重要度，提出来k最短启发式搜索子算法，并且给出了整体算法的实现流程图。

参考文献

[1]汪小帆，李翔，陈关荣.复杂网络理论及其应用.北京：清华大学出版社，2006：180-195.

[2]何大韧，刘宗华，汪秉宏.复杂系统与复杂网络.北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint

摘要：本文针对网络一般算法存在问题，提出来一种基于加权的社会网络重要节点发现算法。该算法基于社会网络中节点和边的属性进行有向加权社会网络建模，融合节点之间相对重要性理论和网络拓扑原理，共同发现加权的社会网络中的重要节点。

关键词：加权 节点 算法

中图分类号：TP39 文献标识码：A 文章编号：1007-9416（2014）08-0133-02

1 概述

不管是社会网络，还是WWW网络，一般介绍的各种算法几乎都是站在整体的角度，或显式或隐式地对网络中所有节点的重要性进行全局的排序，很少有学者关注网络中节点的相对重要性。然而，在数学领域著名的“六度分割理论”形象地揭示了客观世界存在普遍的联系性。在客观世界中，任何两个个体之间哪怕是看起来毫不相干的两者之间都是存在着各种潜在的关系。在对网络节点重要性的研究方面，2000年Chang，Cohn和McCallum提出一种主体敏感性的HITS算法变种，之后人们受到他们的启发提出了基于PageRank算法的个人主体敏感变种算法，虽然这些研究是主要是基于搜索引擎对搜索结果的优化，要达到搜索内容个人主体化的目标，但是他们的算法已经为人们开启了对网络节点相对重要性研究的思想大门。

在研究了Scott White与Padhraic Smyth总结的相对重要性发现框架基础上，我们对其中四种渐进问题的定义做了扩展，让该框架不仅适用于加权网络，让其对有向网络也给予支持。下面给出我们对网络节点相对重要性的定义。

定义1：给出图G（V，E），根节点r和节点t，其中{r，t}G，我们定义非负值I（t|r）为节点t对于根节点r的相对重要性。

定义2：给出图G（V，E），将T（G）中的节点相对于根节点r的重要度进行排序，I（T|r），其中TV。为了到达这一目的，我们先针对每个tT计算I（t|r）值，然后将值进行排序，其中I（t|r）值越大，则说明相对重要性越强。

定义3：给出图G（V，E），一个待排序的节点集合T（G）与一个根节点集合R（G），其中RV，计算所有集合T中的节点对集合R的相对重要性，即I（T|R）。

这里与定义2中一样，要计算I（T|R），其中rR，通常我们需要先分别计算{I（t|r），rR}。比如，我们可以用平均对集合R的相对重要性来定义I（t|R）：

（1）

如果不用平均值的话，我们也可以这样定义I（t|R）=min{I（t|r）：rR}。

定义4：给出图G（V，E），要求出说有节点的相对重要程度，我们只需将R与T都设置为V，即R=T=V。

从上述对四种渐进问题的定义，我们不难看出该定义具有较强的适用性，不仅可以将该思想应用于大型网络的小社区重要节点发现，而且可以进行全局重要节点挖掘。

2 对网络节点权值的定义

对于双加权社会网络中节点权重的定义问题，国内外学者们都曾从不同的角度给出很多种不同的定义，在本文中，我们主要考虑的是社会网络，因此我需要更多的考虑是节点（大多时候是用户或个体），在网络中的声望或者活跃情况。而社会网络中某个节点越是活跃，他越是能够带动影响越多的节点，一起参与到网络交互当中，故此我们可以用一个节点的活跃度来作为社会网络节点的权值大小指标。活跃度在社会网络中的表现形式可以是打电话、发信息、聊天、聚餐、郊游等等，只要是发生在网络中某个节点上的事件。我们都可以视为是该节点活跃度的一个展现方面，将这些事件进行网络全局的归一处理，即可得到我们在要的加权社会网络节点的权值。结合上文所阐述的内容，我们给出网络节点权值的一般定义，设网络个体i提交发布的总消息或资源等交互总数为Mi，使用该在线社交网络平台的时长为Ti（天）。则在网络中该个体的活跃度可以被定义为。

然而，虽然上述定义能够在一定程度上，描述该网络个体的活跃情况，但是，在在线社交网络中，很有可能会出现用户注册时间很短，却在短时间内大量的进行网络交互行为，然而，往往绝大多数用户是保持在一个较低的活跃度水平上的，由此可见该定义所描绘的活跃度，并不能更好的展现一个节点的真实活跃情况。

针对上述原因，我们提出一种新的加权网络节点权值定义方法，定义如公式2所示。

（2）

其中为在近某一个标准时间段T内，网络个体i所发出的所有交互总数，为个体活跃度的调节因子。之所以如此定义，原因上文虽然提到一部分，然而，其主要原因是因为在实际处理真实网络数据集时，我们遇到很多异常个体，为了让所有网络个体都能够有个展现其活跃情况的刻画指标，而且该活跃指标又不能因个体的差异产生较大的起伏，因此结合了数理归一相关理论知识，我们将时间的概念弱化，采用统一时间段，这样较少了变量，让活跃度体现的就是该个体的真实活跃情况，并且通过调节因子，让节点活跃度始终保持在大约0小于1的区间之内，从而为下一步有向加权社会网络的重要节点发现提供了坚实的理论基础。

3 基于加权的社会网络重要节点发现算法

在该算法中，针对任一有向图如图1所示，我们将相连的两节点对节点之间的重要度定义，并且令；对于不相邻的任意两节点，如节点与节点，可以看出从到的路径集合包含{，，，}，将相邻的节点间相对重要度定义为两节点间的关系强度，这是因为关系强度是两个用户关注度和重要性的调和平均值，当两值相差较大的时候，调和平均值会比他们的算术平均值更接近较小的那个值。当节点对节点交互较少，而节点对节点交互较多时，那么会造成单向的高强度关系，采用调和平均值能够有效的避免这种情况的出现。另外，在的定义中采用所有用户的平均交互次数作为全局因子，这一措施可以有效的克服小社区的高局部强度效应。

4 结语

本文简单介绍了国内外学者提出的网络重要节点发现算法，对它们的优缺点进行了对比讨论分析。同时指出了这些算法对于发掘社会网络中重要节点的局限性。提出了新的基于加权的社会网络重要节点发现算法，新算法在双加权与有向的基础上，考虑节点与节点间紧密关系程度，节点个体的活跃度以及考虑了任意两节点间的相对重要性。根据新算法提出了评估重要节点的指标，并对算法中的公式进行详细的解释，针对算法中任意节点间相对重要度，提出来k最短启发式搜索子算法，并且给出了整体算法的实现流程图。

参考文献

[1]汪小帆，李翔，陈关荣.复杂网络理论及其应用.北京：清华大学出版社，2006：180-195.

[2]何大韧，刘宗华，汪秉宏.复杂系统与复杂网络.北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint

摘要：本文针对网络一般算法存在问题，提出来一种基于加权的社会网络重要节点发现算法。该算法基于社会网络中节点和边的属性进行有向加权社会网络建模，融合节点之间相对重要性理论和网络拓扑原理，共同发现加权的社会网络中的重要节点。

关键词：加权 节点 算法

中图分类号：TP39 文献标识码：A 文章编号：1007-9416（2014）08-0133-02

1 概述

不管是社会网络，还是WWW网络，一般介绍的各种算法几乎都是站在整体的角度，或显式或隐式地对网络中所有节点的重要性进行全局的排序，很少有学者关注网络中节点的相对重要性。然而，在数学领域著名的“六度分割理论”形象地揭示了客观世界存在普遍的联系性。在客观世界中，任何两个个体之间哪怕是看起来毫不相干的两者之间都是存在着各种潜在的关系。在对网络节点重要性的研究方面，2000年Chang，Cohn和McCallum提出一种主体敏感性的HITS算法变种，之后人们受到他们的启发提出了基于PageRank算法的个人主体敏感变种算法，虽然这些研究是主要是基于搜索引擎对搜索结果的优化，要达到搜索内容个人主体化的目标，但是他们的算法已经为人们开启了对网络节点相对重要性研究的思想大门。

在研究了Scott White与Padhraic Smyth总结的相对重要性发现框架基础上，我们对其中四种渐进问题的定义做了扩展，让该框架不仅适用于加权网络，让其对有向网络也给予支持。下面给出我们对网络节点相对重要性的定义。

定义1：给出图G（V，E），根节点r和节点t，其中{r，t}G，我们定义非负值I（t|r）为节点t对于根节点r的相对重要性。

定义2：给出图G（V，E），将T（G）中的节点相对于根节点r的重要度进行排序，I（T|r），其中TV。为了到达这一目的，我们先针对每个tT计算I（t|r）值，然后将值进行排序，其中I（t|r）值越大，则说明相对重要性越强。

定义3：给出图G（V，E），一个待排序的节点集合T（G）与一个根节点集合R（G），其中RV，计算所有集合T中的节点对集合R的相对重要性，即I（T|R）。

这里与定义2中一样，要计算I（T|R），其中rR，通常我们需要先分别计算{I（t|r），rR}。比如，我们可以用平均对集合R的相对重要性来定义I（t|R）：

（1）

如果不用平均值的话，我们也可以这样定义I（t|R）=min{I（t|r）：rR}。

定义4：给出图G（V，E），要求出说有节点的相对重要程度，我们只需将R与T都设置为V，即R=T=V。

从上述对四种渐进问题的定义，我们不难看出该定义具有较强的适用性，不仅可以将该思想应用于大型网络的小社区重要节点发现，而且可以进行全局重要节点挖掘。

2 对网络节点权值的定义

对于双加权社会网络中节点权重的定义问题，国内外学者们都曾从不同的角度给出很多种不同的定义，在本文中，我们主要考虑的是社会网络，因此我需要更多的考虑是节点（大多时候是用户或个体），在网络中的声望或者活跃情况。而社会网络中某个节点越是活跃，他越是能够带动影响越多的节点，一起参与到网络交互当中，故此我们可以用一个节点的活跃度来作为社会网络节点的权值大小指标。活跃度在社会网络中的表现形式可以是打电话、发信息、聊天、聚餐、郊游等等，只要是发生在网络中某个节点上的事件。我们都可以视为是该节点活跃度的一个展现方面，将这些事件进行网络全局的归一处理，即可得到我们在要的加权社会网络节点的权值。结合上文所阐述的内容，我们给出网络节点权值的一般定义，设网络个体i提交发布的总消息或资源等交互总数为Mi，使用该在线社交网络平台的时长为Ti（天）。则在网络中该个体的活跃度可以被定义为。

然而，虽然上述定义能够在一定程度上，描述该网络个体的活跃情况，但是，在在线社交网络中，很有可能会出现用户注册时间很短，却在短时间内大量的进行网络交互行为，然而，往往绝大多数用户是保持在一个较低的活跃度水平上的，由此可见该定义所描绘的活跃度，并不能更好的展现一个节点的真实活跃情况。

针对上述原因，我们提出一种新的加权网络节点权值定义方法，定义如公式2所示。

（2）

其中为在近某一个标准时间段T内，网络个体i所发出的所有交互总数，为个体活跃度的调节因子。之所以如此定义，原因上文虽然提到一部分，然而，其主要原因是因为在实际处理真实网络数据集时，我们遇到很多异常个体，为了让所有网络个体都能够有个展现其活跃情况的刻画指标，而且该活跃指标又不能因个体的差异产生较大的起伏，因此结合了数理归一相关理论知识，我们将时间的概念弱化，采用统一时间段，这样较少了变量，让活跃度体现的就是该个体的真实活跃情况，并且通过调节因子，让节点活跃度始终保持在大约0小于1的区间之内，从而为下一步有向加权社会网络的重要节点发现提供了坚实的理论基础。

3 基于加权的社会网络重要节点发现算法

在该算法中，针对任一有向图如图1所示，我们将相连的两节点对节点之间的重要度定义，并且令；对于不相邻的任意两节点，如节点与节点，可以看出从到的路径集合包含{，，，}，将相邻的节点间相对重要度定义为两节点间的关系强度，这是因为关系强度是两个用户关注度和重要性的调和平均值，当两值相差较大的时候，调和平均值会比他们的算术平均值更接近较小的那个值。当节点对节点交互较少，而节点对节点交互较多时，那么会造成单向的高强度关系，采用调和平均值能够有效的避免这种情况的出现。另外，在的定义中采用所有用户的平均交互次数作为全局因子，这一措施可以有效的克服小社区的高局部强度效应。

4 结语

本文简单介绍了国内外学者提出的网络重要节点发现算法，对它们的优缺点进行了对比讨论分析。同时指出了这些算法对于发掘社会网络中重要节点的局限性。提出了新的基于加权的社会网络重要节点发现算法，新算法在双加权与有向的基础上，考虑节点与节点间紧密关系程度，节点个体的活跃度以及考虑了任意两节点间的相对重要性。根据新算法提出了评估重要节点的指标，并对算法中的公式进行详细的解释，针对算法中任意节点间相对重要度，提出来k最短启发式搜索子算法，并且给出了整体算法的实现流程图。

参考文献

[1]汪小帆，李翔，陈关荣.复杂网络理论及其应用.北京：清华大学出版社，2006：180-195.

[2]何大韧，刘宗华，汪秉宏.复杂系统与复杂网络.北京：高等教育出版社，2009：126-183.

[3]Barabási A L. Network science： Luck or reason[J].Nature， 2012，489（7417）：507-508P.

[4]Redner S. How popular is your paper？An empirical study of the citation distribution[J]. The European Physical Journal B-Condensed Matter and Complex Systems，1998，4（2）：131-134P.endprint