刘尹平，王笃会，任朝阳

　　（南京邮电大学 通信与信息工程学院，江苏 南京 210003）

　摘要：在线社交网络是伴随着互联网技术发展产生的，它属于众多复杂网络中的一种。近年来，对于在线社交网络的研究不断深入，研究方向可以细分为网络拓扑特征的分析、虚拟社区划分算法的研究、传播动力学研究、网络采样与重构、网络拓扑识别等。大数据研究的兴起使得在线社交网络的研究更加受到人们的关注。当前，人们的日常生活几乎离不开在线社交网络，也因此每天都会有大量的用户数据产生，分析、利用这些数据可以帮助人们了解自己并创造更多的价值。

　关键词：在线社交网络；拓扑特征；虚拟社区划分算法；采样;重构；大数据

0引言

　　BOCCALETTI S等人［1］2006年发表的文章中，从复杂网络结构特征、动力学两个角度对复杂网络进行了理论研究及具体应用分析。在国内，方锦清等人将复杂网络的相关研究定义为一门新的交叉科学——网络科学［2］，其涉及图论、统计物理学、现代控制理论、非线性科学等诸多领域的研究理论。

　　社交网络是一种常见的复杂网络，是指由许多节点构成的一种社会结构，可以抽象为由多个节点及节点之间的链路构成的图，它是伴随着人类的诞生而产生的，这里的节点可以是个人也可以是组织，节点之间的链路对应于各种社会关系，比如朋友关系。

　　在线社交网络是互联网与传统社交网络的结合，是一种在信息网络上由社会个体集合及个体之间的连接关系构成的社会性结构，它的产生与计算机技术的飞速发展息息相关。这种社会性结构也可以抽象为由节点和链路构成的图。节点可以是个人或者组织，也可以是网络ID等虚拟个体，链路则代表各种社会关系，或者收发消息等多种动作行为［3］。

　　复杂网络、社交网络、在线社交网络三者的关系可以理解为，社交网络为复杂网络的一种，因此具有许多复杂网络的特征，而在线社交网络可以理解为一种特殊的社交网络。因此，在线社交网络也具有复杂性，其复杂性主要表现在以下三个方面：（1）节点的复杂性，网络中每一个节点都具有不同的属性、特征，同一个节点还可能具有复杂的时间演化行为。（2）结构复杂性，具体来说，就是网络节点之间关系混乱，连接交错复杂，且随时可能发生动态变化。比如，你会在不断改变的生活环境中不断地结交一些新朋友，同时也可能失去一些朋友。（3）结构与节点之间相互影响，比如，朋友圈的组成结构影响你的言行举止，而你结交新的朋友就会改变你朋友圈的结构。图1描述了社交网络的生长过程。

　　近年来，对于在线社交网络的研究不断深入，研究方向可以细分为网络拓扑特征的分析、虚拟社区划分算法的研究、传播动力学研究、网络采样与重构、网络拓扑识别等。

1在线社交网络的拓扑特性分析

　　在线社交网络可以是无向网络也可以是有向网络，MSN、QQ、微信等在线实时通信平台需要双方认证才可以建立朋友关系，基于这种方式形成的在线社交网络结构中链路是无向的，而通过Twitter、微博等可以建立单向的关系，比如在新浪微博中，你可以关注自己喜欢的明星但明星并不一定会关注你，这样就会形成有向在线社交网络。

　　1.1无标度特性

　　在无向网络中节点的度指网络中与该节点直接相连的边的数目，度分布P（k）定义为一个随机选择的节点度为k的概率，也就是网络中度为k的节点数目与网络节点总数目的比值。

　　无标度的概念是BARABSI A L和ALBERTT R［4］提出的。经研究发现，现实生活中的许多复杂网络的节点度分布函数服从幂律分布，其表现为，大部分的节点拥有的邻居节点数很少，只有少部分的节点拥有大量的邻居节点。由于幂律分布函数具有无标度性质，因此又称这种特征为“无标度”特性。在线社交网络作为复杂网络中的一种，也具有无标度特性。

　1.2小世界特性

　　在无权网络中，从一个节点到另一个节点的路径需要经过的边数称为两节点间的距离。当网络中两节点之间存在不止一条路径时，其中距离最短的一条称为连接两节点的最短路径，此距离即为最短路径长度。N个节点构成的网络中任意两节点间距离的均值定义为整个网络的平均路径长度。

　　“小世界”概念由社会心理学家MILGRAM S提出，来自于其曾进行的一次“邮件传播”的实验，也被称为“六度分割”理论。WATTS D J和STROGATZ S H 1998年第一次提出了小世界模型［5］。在线社交网络拥有大量的节点和链路，网络拓扑十分复杂，但令人惊讶的是，任意两节点的最短路径和网络平均路径都非常小，这种现象被形象地称为“小世界”特征。研究表明，2010年人人网的用户之间的平均距离为5.38［6］，而2011年全球Facebook上两个用户之间的平均距离仅为4.74。然而，对于网络“小世界”特性的研究均基于无权网络，并没有考虑网络中节点连接的强弱不同。

　　真实的在线社交网络的特性不仅局限于无标度特性与小世界特性，有些在线社交网络还具有聚类特性、社区结构特性等。因此，建立真实社交网络的模型仍存在挑战。

2在线社交网络虚拟社区划分

　　在线社交网络由若干“群”或“簇”构成。这些群或簇的内部节点连接紧密，而群或簇间的连接则相对比较稀疏。也就是说，在线社交网络与诸多复杂网络一样，具有“社区结构”的特征［7］。

　　目前，对于社区结构的定义有许多不同的方法，比如：如果图G内所有节点间连接的度的总和大于其与其他部分图相连的度的总和，则图G为一个社区结构［1］。不同的定义方法对应着不同的虚拟社区划分算法，具体来说，虚拟社区划分算法有两类，一类是静态虚拟社区划分算法，另一类是动态虚拟社区划分算法。

　　经典的静态虚拟社区划分算法包括Kmeans算法、分裂算法、凝聚算法、谱分析算法等［8］。其中，Kmeans算法是最知名的聚类算法，该算法给出一组欧几里得节点并根据节点数目给出一个正整数k，将数据集划分为k个不相交的子集。计算机根据k值随机选择k个点作为初始中心点，计算所有节点到k个中心点的平方欧式距离并将节点归于距离最短的那个集群。重新计算k个集群的中心点并进行迭代，使得所有点到中心点的平方欧式距离之和最短，同时不同集群中心点的距离最长。这种算法可以实现较好的划分效果，但k值需要人为估计。

　　对于动态虚拟社区的划分，当前的一个普遍方法是将连续时间分割成一些离散的时间步，分别抽取社区结构，然后引入演化特征来解释随时间的变化这些划分之间的差异，从而得到网络和其中社区的发展趋势。

　　在线社交网络的虚拟社区划分可以应用于广告的精准投放，将相似的人群划分在同一社区，针对不同社区投放不同的广告，以减少成本增加商业利润。此外，虚拟社区划分也可用于在线社交网络的推荐系统，同一社区的节点属性更具有相似性，因此也更有可能成为朋友。

3在线社交网络上的传播动力学

　　复杂网络的动力学定义为，网络在“外部刺激”的推动下，或者“内部消息”的触发下，节点自身信息状态改变或者节点间连接关系发生变化，从而导致整个网络发生明显的或者不明显的“质变”，这种改变可以是在某种规则约束下执行的，也可能是随机的。

　　传播是一种常见的网络动力学行为［9］。目前，关于在线社交网络上传播动力学研究的文章有许多，比如对于微博中的谣言传播的研究。在线社交网络上传播的不仅只有谣言，也可以是口碑、情绪等。研究传播动力学的前提是对在线网络进行建模，基于代理的建模是其中一种常见的方法，即利用现有的计算机技术建立基于代理的网络模型，该模型由许多自治的、相互交互的“代理”组成。代理具有自身的行为，也可与其他代理进行交互，这种交互会影响代理自身的行为。根据模型应用环境的不同，模型中的代理可以代表个人、家庭、公司甚至是国家。基于代理的建模采用“自底向上”的建模思想，通过对一个个代理的建模，就可以将不同代理的属性和行为的多样性从整个系统的行为中表现出来。

　　研究在线社交网络上的传播动力学有着重要的实际意义，例如，研究谣言在在线社交网络中的传播过程、传播规律可以为政府及有关部门的征兆预警、判断分析及公共宣传工作提供保障。因此，研究不同类型的信息在在线社交网络中的传播过程，揭示信息传播的一般规律与特性，提出科学有效的控制策略，是传播研究领域的重要课题。

4在线社交网络采样与重构

　　参考文献［10］中指出，网络采样与网络重构与网络构建的发展趋势密切相关。一方面，由于受到现有技术的限制，对于许多网络只能通过采样的方法获得数据；另一方面，即使能够获得完整的数据，有些网络问题的研究也需要对网络进行采样。例如，研究在线社交网络上的传播动力学问题时，一般只在部分子网络进行研究。此外，在处理大规模数据可视化的问题时也需要有效的采样。

　　目前被广泛应用的采样算法有广度优先采样、Frontier采样、Forest Fire采样等。每种采样算法都有其优缺点，以FF(Forest Fire)采样算法为例，FF采样算法基于随机游走思想，它首先随机地选取一个节点作为森林火灾的发源地，然后选取与该节点的邻居节点作为下一步有可能被烧到的树木，每一个节点（树木）被烧到的概率为P，P的大小决定了抽样效果的好坏，文献［11］指出P=0.8时抽样的效果最好。FF算法采集的子网虽然连通性较好，且具有小世界特性，但由于更倾向于获取度值较大的节点，因此样本节点之间的连接将逐渐具有超线性关系，所以无法实现对原始网络的真实采样。

　　与网络采样相对应的一个问题是网络重构(Network Reconstruction)，即能否以及如何从部分网络数据推测得到整个网络的数据。这一问题也被称为网络完整性(Network Completion)、网络推断(Network inference)或逆向工程网络(Reverse Engineering Network)。

　　网络重构的问题最早由GUIMER R和SALESPARDO M提出［12］，他们基于随机分块模型来进行网络重构，随机分块模型的基本思想是将节点分为相互独立的组，两个节点之间存在链路的概率只与节点所在的组有关，文献［12］中指出，不仅可以预测两个未连接的节点之间是否存在链路，同时也可以判断网络中存在的虚假边。链路预测也是网络重构相关的研究之一，链路预测的主要思想是利用节点之间属性相似性或者网络结构的相关性等来恢复丢失连边［13］，例如基于共同邻居指标的链路预测，即两个节点拥有的共同邻居越多，它们之间存在链路的可能性就越大。链路预测技术可用于在线社交网络的推荐系统，两个陌生人有很多的共同朋友或者拥有许多的共同爱好，那么他们能够成为朋友的概率就很大。

5在线社交网络拓扑识别

　　近年来，无论是对复杂网络还是对具体的在线社交网络的研究，大多是研究网络拓扑结构在已知条件下的网络动力学问题，或者是研究网络结构的各种特征参数，如平均距离、度分布等对网络动力学的影响［14］。然而实际的网络存在各种不确定性的信息，网络的节点数目、拓扑连接等往往只有部分已知，并且还可能不断地变化。假设网络动力学演化是可以测量获取的，那么能否根据网络动力学演化来估计网络的拓扑结构，是一个极具挑战性的问题。如果说在已知网络拓扑结构条件下研究网络动力学问题是正问题的话，那么对于网络拓扑结构的识别则属于反演问题（或者反问题）。显然，反问题比正问题困难，而且一般来说反问题的解是不唯一的，解反问题是需要附加补充条件的。

　　对于网络的拓扑结构识别问题，目前国内已经取得一些重要进展。陆君安等人提出基于自适应同步的网络动力学参数和拓扑识别方法［15］，指出动力学信息对于拓扑识别并非是充分的，为了识别网络拓扑结构，需要满足经内连耦合动力学映射后的一簇函数组在同步流形上线性无关的条件。如果需要同时识别网络拓扑结构和动力学参数，则需要满足经内连耦合动力学和节点动力学映射后的两簇函数组在同步流形上线性无关的条件。对于具体的在线社交网络，可以考虑利用其上的传播等动力学行为推测其具体结构，进一步研究动力学行为与网络结构之间的相互影响。

　　6结论

　　在线社交网络各方面的研究目前已经取得了相当多的研究成果，同时也受到了越来越多人的关注与投入，在线社交网络研究与大数据研究的结合是当前的一个研究热点，未来将会有更好的发展与应用。

　　大数据是指无法在一定时间内用常用软件工具对其内容进行抓取、管理和处理的数据集合［16］。2013年新浪公司全年财报中指出，截至2013年12月份，新浪微博注册用户数达2.81亿，微博活跃用户数达1.67亿，每天产生约2亿条微博数据。2012年3月美国政府发布《大数据研究和发展倡议》，时至今日，大数据显然已成为一种竞争资源。在线社交网络每天都有大量数据产生，如何利用这些数据，结合已有的在线社交网络理论研究成果，分析人们的生活和行为，挖掘政治、社会、文化、商业、健康等领域的信息，以便于更好地服务于用户并从中获利，将具有广阔发展前景。

参考文献

　　［1］ BOCCALETTI S, .LATORA V, MORENO Y, et al．Complex network:structure and dynamics ［J/OL］．Physics Reports,2006,424:17530.［20160320］.http://www.sciencedirect.com/science/article/pii/S037015730500462X.

　　［2］ 方锦清，汪小帆，郑志刚，等．一门崭新的交叉科学：网络科学（上）［J］．物理学进展，2007，27（3）：239343．

　　［3］ 方滨兴，许进，李建华，等．在线社交网络分析［M］．北京：电子工业出版社，2014．

　　［4］ BARABáSI A L, ALBERT R. Emergence of scaling in random networks［J/OL］.Science ,1999,286(5439):50912.［20160320］.http://science.sciencemag.org/content/286/5439/509.

　　［5］ WATTS D J, STROGATZ S H. Collective dynamics of smallworld networks［J/OL］. Nature, 1998,393(6684):440442. ［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=9&SID=N2CCOYPK3reQ14t9giD&page=1&doc=3.

　　［6］ Jiang Jing，WILSON C，Wang Xiao，et al．Understanding latent interactions in online social networks ［J/OL］.ACM Transactions on the Web，2010,7(4):369382.［20160320］.http://apps.webofknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=6&SID=N2CCOYPK3reQ14t9giD&page=1&doc=1.

　　［7］ 郑浩原，黄战．复杂网络社区挖掘———改进的层次聚类算法［J ］．微型机与应用，2011，30（16）：8588．

　　［8］ 顾宏博，奚杰杰，吴晶．基于关联系数的社区划分算法［J］．微型机与应用，2015，34（18）：1719．

　　［9］ MORENO Y, NEKOVEE M, PACHECO A F. Dynamics of rumor spreading in complex networks［J/OL］. Physical Review E, 2004, 69(6 Pt 2):066130. ［20160320］.http://journals.aps.org/pre/abstract/10.1103/PhysRevE.69.066130.

　　［10］ 汪小帆．网络科学发展研究［J］．学科发展报告，2013，36（4）：111119．

　　［11］ LESKOVEC J，FALOUTSOS C．Sampling from large graphs［C］．The Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2006：2023.

　　［12］ GUIMERà R，SALESPARDO M．Missing and spurious interactions and reconstruction of complex network［C］．Proceeding of National Academy of Science of the United States of America，2009：2207322078.

　　［13］ 吕琳媛，周涛．链路预测［M］.北京：高等教育出版社，2013．