龙源期刊网 http://www.qikan.com.cn
社会网络中的影响力综述
作者：夏涛等
来源：《计算机应用》2014年第04期
摘 要：在社会影响力传播领域，社会网络作为媒介在社会个体之间相互影响、传播信息与观点方面发挥着根本性的作用。首先讨论了社会影响力的定义，以及社会影响力作为一种社会相关性的本质属性；然后分析阐述了影响力最大化问题中的级联模型和线性阈值模型以及能够确定具有影响力个体的贪心算法和探索式算法；最后对影响力研究的新趋势，诸如基于社区结构的影响力最大化算法以及讨论多个主题、多种行为的影响力研究进行了分析。 关键词：社会影响力；影响力最大化；社会网络；社会相关性；社区结构 0 引言
随着互联网技术的发展，越来越多的虚拟社会相继出现，如大型社交网络网站、通过手机通信形成的人际关系网络等。透过这些社会网络所展现出的社会关系和人际互动是许多研究的重点，在社会个体影响力传播领域，社会网络作为媒介，在社会个体之间相互影响、传播信息与观点方面，发挥着根本性的作用。一个信息体或是观点可以在人群中快速广泛地蔓延开来，也有可能迅速地消失，如果想要了解信息被人们接受的程度，就应该重点了解信息传播是如何在基本的社会网络中动态展现的：在何种程度上人们可能被他们的朋友或同事的判断影响，在何种程度上“口碑效应”将会发生。
“口碑效应”和“病毒式营销”中的影响力模型研究是近年来社会网络分析领域的研究热点之一。“病毒式营销”最初只针对少数有“影响力”的顾客，将某一产品首先介绍给这一群体，然后引起一连串的影响，大多数成员会将此产品推荐给他的朋友，通过“口碑效应”使这一产品得到推广。这种首先找到一定数量的具有“影响力”的节点，然后通过这些具有“影响力”的节点去影响别的节点的问题称之为影响力最大化问题。影响力最大化问题被Richardson等[1]引入到社会网络领域后引起了很多学者的关注，作者给出了影响力最大化问题的详细定义，并且给出了关于影响力最大化的评价指标，为后来学者的研究提供了借鉴。Kempe等[2]第一次比较系统地研究了影响力最大化模型，文献中系统地总结了影响力最大化问题，并且详细总结了影响力最大化模型：级联模型（Independent Cascade，IC）和线性阈值模型（Linear Threshold，LT）。
目前有不少研究者对多主题、多行为以及基于社区结构的影响力展开研究。多主题的研究主要是对网络中的各个主题进行单独影响力的计算，然后对结果进行分析；多行为的研究主要是对网络中节点所从事的各个行为进行影响力的计算；基于社区结构的影响力研究主要是利用社区结构特性把整个网络划分成若干个社区，然后对每个社区运用影响力最大化模型找到初始节点，最后对找到的节点进行分析、处理找到符合要求的节点。
龙源期刊网 http://www.qikan.com.cn
混杂因素和影响力、同质性有明显区别。首先，影响力的定义很明确：一个人受到他的已经激活的邻居节点的影响从而激活；而对于混杂因素来说，一个节点的激活是一些不被发现的因素导致的，并不是像影响力那样。同样，同质性也有明确定义：具有共同点的个体更容易成为朋友；而混杂因素中，两个节点成为朋友可能是由一些没有发现的因素导致的。
Anagnostopoulos等在文献[7]中证明了社会影响力是社会相关性的一种，以及社会影响力在社会中发挥着作用。Anagnostopoulos等给出了社会影响力的含义，这对社会网络中社会影响力的定性研究有着很大帮助；同时还提出两种能够证明社会影响力确实在社会网络中发挥作用的方法Shuffle和EdgeReversal。 2.1 影响力最大化问题的描述
影响力最大化问题可以概括为：给定一张社会网络传播图、一种特定的影响力，如何确定一个指定大小的节点集合当集合里面的节点在初始时刻被激活时，遵循传播模型的传播机制，最终能在网络上激活最多的节点。
实际问题中影响力最大化问题可以描述为：销售商首先通过一定的手段使得网络中的一部分人开始接受某种新上市的产品，接下来由于朋友之间的口碑推荐，在网络中该产品的使用会像病毒一样蔓延，在很短的时间里达到传统营销无法达到的效果。
影响力最大化的符号描述：给定一个社会网络传播图G（V，E），其中：V是网络中存在的节点，E是任意连个节点之间的边。在影响力最大化问题中规定每个节点只有两个状态：激活和未激活，节点的状态转变具有单调性，即每个节点只能由未激活状态转变为激活状态而不能由激活状态转变为未激活状态；任意节点V只能由它相邻的并且已经被激活的节点所激活。
令k表示一个指定的节点集合A的数目；集合A是初始集合，且A中的节点都处于激活状态；定义节点A的影响力σ（A）表示在传播结束后A所影响的节点数目。所以影响力最大化问题的符号描述为：对于给定的传播网络图G（V，E），首先找到包含k个初始节点的集合A，然后A去影响G（V，E）中的其他节点，最后得到被A影响的节点集σ（A）。 贪心算法求解影响力最大化问题结构简单，易于理解，其最大的优点就是能够得到稳定的解，算法的结果至少能保证得到最优解的63%。但贪心算法也有很严重的缺点：它的时间复杂度很高。贪心算法的时间复杂度为O（kRmn），其中：k为种子节点的个数，R为模拟传播图的张数，m为社会网络中边的个数，n为社会网络中节点的个数。贪心算法用来计算几百个节点的社会网络需要相当长的时间去搜索，更不适合成千上万个节点的大型网络。
自基本贪心算法被提出以后，很多研究者对其进行了改进：如Leskovec等[9]提出的CELF算法运用影响力最大化问题的子模特性，很大程度上降低了评价节点影响力传播工作的次数，
龙源期刊网 http://www.qikan.com.cn
CELF方案的运行速度比基本的贪心算法快700多倍。除此之外，还有Chen等[10]提出的NewGreedy算法和MixGreedy算法等。 2.3.2 探索式算法
贪心算法的高时间复杂度使其在大型网络的应用受到，一种可能的方法就是使用探索式算法。在社会网络分析中，度和一些其他的基于中心性的探索式算法经常被用来评价节点的影响力。
影响力最大化问题中节点度经常被用来选择初始节点。在文献[2]的实验中选择具有最大度数的节点为种子节点，能够比其他探索式算法得到较大的影响力传播，但是还是不能和贪心算法那样得到比较好的效果。 3.1 研究现状
目前，社会网络中的影响力主要研究方向有：1）寻找以及确定具有影响力的个体；2）影响力最大化问题。其中，第二个研究方向包含第一个研究方向，因为影响力最大化问题首先要解决的问题是找到种子节点，即具有影响力的节点。
关于如何确定具有影响力的个体，前面作了一个简要的介绍。关于这方面的研究，提出了很多方法，其中主要有：
1）degree centrality：这是最简单的中心度量，度比较大的节点就是有影响力的节点。 2）closeness centrality：这是方法1）的延伸，主要考虑一个节点与网络中其他节点的紧密程度。
3）betweenness centrality，主要考虑节点的最短距离。
关于这方面的算法，主要是前文介绍的贪心算法和探索式算法，另外还有基于社区结构的算法。贪心算法和探索式算法可以看成是全局算法；而基于社区结构的算法是局部算法，这种算法的核心思想就是将整个网络划分成若干个网络进行影响力节点的确定，有关这种算法下面内容会详细地描述。
影响力最大化问题自Richardson和Domingos提出就一直是研究的热点内容。其中最经典的模型就是级联模型和线性阈值模型，而且目前大部分使用的模型也是这两个，很少有人提出新的模型。
目前很多研究以及实验对多主题以及多行为的影响力进行了探索，这部分研究主要对每个主题间的影响力进行相关性等方面的分析，从而对网络中的影响力有一个整体的了解。下面选择了比较有代表性的文献资料对这一方面进行描述。
龙源期刊网 http://www.qikan.com.cn
3.2 多个主题影响力研究
Cha等[11]研究多主题影响力内容比较早，主要介绍了使用Twitter网站上的数据进行的影响力实验。
实验中Cha等主要对用户节点的indegree、retweet和mention三个主题进行研究，其中：indegree代表了一个节点的入度数，表示有多少观众关注该节点；retweet代表一个节点的tweet被转发的数量；mention代表了一个节点被提及的数量。
实验中分别求出每个主题中每个节点的影响力，值得注意的是，文献[11]中所求影响力并不是给出具体的影响力大小的值，而是根据每个主题的数量把影响力分等级。等级1表明最有影响力，数字越大表明影响力越小。对于不同主题的相关性问题，实验中用Spearmans rank correlation coefficient（斯皮尔曼等级相关系数）来解决。
Spearmans rank correlation coefficient是衡量两个变量的依赖性的指标。该系数对原始变量分布不作要求，属于非参数统计方法。它利用单调方程评价两个统计变量的相关性。Spearmans rank correlation coefficient的定义如下： 4 结语
本文对社会影响力作了一个简要的总结，目前对于社会影响力的研究主要分为两个大的方向：1）发现以及确定具有影响力的个体；2）影响力最大化问题。其中第一个研究方向可以看成第二个研究方向的一个部分。
根据目前社会网络中影响力的研究现状，可以对未来这部分的研究作一个推测：如何更高效、更快速地发现具有影响力的个体。现有的算法如贪心算法具有很好的效率但算法的时间复杂度很高不适于大型的社会网络；探索式算法相比贪心算法来说，时间复杂度好了很多但效率却不尽如人意；影响力最大化问题中模型的优化以及新模型的提出；对网络中不同角度的影响力的研究，像多个行为以及多个主题之间的影响力的分析，能够对社会网络中的影响力有整体性的了解，以及通过各个主题之间的对比，能够使决策者作出更有效的决策。 参考文献：
[1]RICHARDSON M， DOMINGOS P. Mining knowledgesharing sites for viral marketing [C]// KDD 02： Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2002： 61-70.
[2]KEMPE D， KLEINBERG J， TARDOS . Maximizing the spread of influence through a social network [C]// KDD03： Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 137-146.
龙源期刊网 http://www.qikan.com.cn
[3]FOWLER J H， CHRISTAKIS N A. Dynamic spread of happiness in a large social network： longitudinal analysis over 20 years in the Framingham heart study [J]. British Medical Journal， 2008， 337（a2338）： 1-9.
[4]DUNBAR R. Neocortex size as a constraint on group size in primates [J]. Journal of Human Evolution， 1992， 22（6）： 469-493.
[5]BACKSTROM L， HUNTTENLOCHER D， KLEINBERG J， et al. Group formation in large social networks： membership， growth， and evolution [C]// KDD 06： Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2006： 44-54.
[6]MARLOW C， NAAMAN M， BOYD D， et al. HT06， tagging paper， taxonomy， Flickr， academic article， to read [C]// HYPERTEXT 06： Proceedings of the Seventeenth Conference on Hypertext and Hypermedia. New York： ACM， 2006： 31-40.
[7]ANAGNOSTOPOULOS A， KUMAR R， MAHDIAN M. Influence and correlation in social networks [C]// KDD08： Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2008： 7-15.
[8]ARAL S， MUCHNIK L， SUNDARARAJAN A. Distinguishing influencebased contagion from homophilydriven diffusion in dynamic networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2009， 106（51）： 21544-21549.
[9]LESKOVEC J， KRAUSE A， GUESTRIN C. Costeffective outbreak detection in networks [C]// KDD07： Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429.
[10]CHEN W， WANG Y， YANG S. Efficient influence maximization in social networks [C]// KDD09： Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 199-208.
[11]CHA M， HADDADI H， BENEVENUTO F， et al. Measuring user influence in Twitter： the million follower fallacy [C]// ICWSM 2010： Proceedings of the 4th International AAAI Conference on Weblogs and Social Media. Menlo Park， California： AAAI Press， 2009： 11-13.
[12]TANG J， SUN J，WANG C. Social influence analysis in largescale networks [C]// KDD09：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 807-816.
龙源期刊网 http://www.qikan.com.cn
[13]GOYAL A， BONCHI F， LAKSHMANAN L V S. Learning influence probabilities in social networks [C]// WSDM 10： Proceedings of the Third ACM International Conference on Web Search and Data Mining. New York： ACM， 2010： 241-250.
[14]GALSTYAN A， MUSOYAN V， COHEN P. Maximizing influence propagation in networks with community structure [J]. Physical Review E： Statistical， Nonlinear， and Soft Matter Physics， 2009， 79（5）： 056102-7.
[15]CAO T， WU X， WANG S， et al. OASNET： an optimal allocation approach to influence maximization in modular social networks [C]// SAC10： Proceedings of the 2010 ACM Symposium on Applied Computing. New York： ACM， 2010： 1088-1094.
[16]WANG Y， CONG G， SONG G， et al. Communitybased greedy algorithm for mining topK influential nodes in mobile social networks [C]// KDD10： Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 1039-1048.
