论文部分内容阅读
摘 要 本文综述了一些大规模在线社会网络表现出来的无标度和小世界特性、高聚类系数及社团结构等性质，阐明了在线社会网络结构的一些方法。
关键词 在线社会网络 拓扑结构
中图分类号：TP393 文献标识码：A
一、引言
社会网络是一群人或团体按某种关系连接在一起而构成的一个系统，如个人之间的朋友关系、同事之间的合作关系、家庭之间的联姻关系和公司之间的商业关系等等。Milgram小世界实验研究了人际关系在某种程度上反映出的小世界特征，得出了著名的六度分离推断。随着互联网的快速发展，各种在线社会网络如雨后春笋般涌现，最具代表性的平台包括在线交友网络（如facebook、MSN、微信）、社交网（如人人网）、BBS和论坛、博客、Wik等等。在线社会网络是指人们通过以计算机为中介的交际活动，相互联系和协作，并组成在线社区的网络。在线社会网络是围绕用户来组织的，用户参与到一个网络或社区中，发布文本、图片等形式的信息，也可建立与他人的链接。
二、在线社会网络中的拓扑结构
自从Watts和Strogatz教授发表“‘小世界’网络的集体动力学”，揭示了复杂网络的小世界特征，以及Barabasi和Albert建立无标度模型以来，人们对网络拓扑结构模型进行了研究。本文所关注的社会网络是各种基于因特网的在线网络。哈佛大学的Adamic等人较早开始研究在线社会网络，发现了在线社会网络的小世界特性以及团结构。Liben，Nowell等人通过分析Live30umal的数据得出用户之间的连接和地理位置的关系。Fu等把人人网看作无向网络。整个网络的度分布指数为2.12，其中一个连同子图中节点平均路径长度为3.48，直径为9，聚类系数为0.20，人人网具有小世界特性。
互联网的产生与发展在很大程度上改变了人与人的交流方式，在线社会网络映射与扩展了现实社会网络。胡海波在《在线社会网络的结构、演化及动力学研究》研究了大型在线社会网络Wealink的结构，该网站是国内最早的商务社交网站之一。并得出该网络除了具有小世界特性、高聚类系数、社团性等与一般的现实社会网络相似的共性。Wang等研究了基于P2P通信的Gnutella构建的在线社会网络结构特性，若用户B回答了用户A的提问，则A到B可建立一条有向边，整个网络是有向无权图。
三、在线社会网络结构的发现方法
寻找大规模复杂网络中的社团结构，较典型的算法有计算机科学中最有名的谱平分法和Kernighan-Lin算法，社会学中的GN算法和凝聚算法。近年來，研究者对如何在大规模的在线社会网络中挖掘出社区结构进行了探索。燕飞、张铭等提出了综合行动者兴趣及网络拓扑结构的社区发现方法，即使用兴趣聚类的方法来发现用户的兴趣社区后，再考虑行动者的社会网络结构特征，主要运用社会网络权值计算、行动者间相关度计算和社区扩展，对兴趣社区进行扩展。Clauset、Newman等提出了一种基于贪婪算法思想的社团结构检测算法，CNM算法。该算法的计算采用堆数据结构计算和更新模块度。关于社区结构的检测算法其中有一种是标签传播算法（LPA），其基本思想是在算法开始时，给每个节点初始化一个不同的标签值，给每个节点指定一个标签，在算法进行中，节点将选择与最多邻居的所在社区改变标签。因此随着算法的进行，节点标签也不断变化，直到标签不再改变，则算法结束。
（作者单位：河北大学管理学院）
参考文献：
[1]Barabasi A-L，Albert R.Emergence of scaling in random networks[J].Science，1999.
[2]Adamic et al..A social network caught in the web[J]，First Monday，2003，8（6）：1-22.
[3]Liben-Nowell， D.， Novak， J.， Kumar， R.， Raghavan， P.， & Tomkins， A. （2005） Geographic routing in social networks. Proceedings of National Academy of Sciences， 102 （33） 11，623-11，628.
[4]Fu F， Chen X， Liu L， et a.l Socialdilemmas in an online socialnetwork： the structure and evolution of cooperation[J]. Phys-ics LettersA， 2007， 371（1-2）： 58-64.
[5]胡海波，汪小帆.在线社会网络的结构、演化及动力学研究[D].上海：上海交通大学，2010.
[6]F. Wang， Y. Moreno， Y. Sun， The structure of peer-to-peer social networks， Phys. Rev. E 73 （2006） 036123.
[7]燕飞，张铭，谭裕韦，唐建，邓志鸿.综合社会行动者兴趣和网络拓扑的社区发现方法[J].计算机研究与发展，2010（6）.
关键词 在线社会网络 拓扑结构
中图分类号：TP393 文献标识码：A
一、引言
社会网络是一群人或团体按某种关系连接在一起而构成的一个系统，如个人之间的朋友关系、同事之间的合作关系、家庭之间的联姻关系和公司之间的商业关系等等。Milgram小世界实验研究了人际关系在某种程度上反映出的小世界特征，得出了著名的六度分离推断。随着互联网的快速发展，各种在线社会网络如雨后春笋般涌现，最具代表性的平台包括在线交友网络（如facebook、MSN、微信）、社交网（如人人网）、BBS和论坛、博客、Wik等等。在线社会网络是指人们通过以计算机为中介的交际活动，相互联系和协作，并组成在线社区的网络。在线社会网络是围绕用户来组织的，用户参与到一个网络或社区中，发布文本、图片等形式的信息，也可建立与他人的链接。
二、在线社会网络中的拓扑结构
自从Watts和Strogatz教授发表“‘小世界’网络的集体动力学”，揭示了复杂网络的小世界特征，以及Barabasi和Albert建立无标度模型以来，人们对网络拓扑结构模型进行了研究。本文所关注的社会网络是各种基于因特网的在线网络。哈佛大学的Adamic等人较早开始研究在线社会网络，发现了在线社会网络的小世界特性以及团结构。Liben，Nowell等人通过分析Live30umal的数据得出用户之间的连接和地理位置的关系。Fu等把人人网看作无向网络。整个网络的度分布指数为2.12，其中一个连同子图中节点平均路径长度为3.48，直径为9，聚类系数为0.20，人人网具有小世界特性。
互联网的产生与发展在很大程度上改变了人与人的交流方式，在线社会网络映射与扩展了现实社会网络。胡海波在《在线社会网络的结构、演化及动力学研究》研究了大型在线社会网络Wealink的结构，该网站是国内最早的商务社交网站之一。并得出该网络除了具有小世界特性、高聚类系数、社团性等与一般的现实社会网络相似的共性。Wang等研究了基于P2P通信的Gnutella构建的在线社会网络结构特性，若用户B回答了用户A的提问，则A到B可建立一条有向边，整个网络是有向无权图。
三、在线社会网络结构的发现方法
寻找大规模复杂网络中的社团结构，较典型的算法有计算机科学中最有名的谱平分法和Kernighan-Lin算法，社会学中的GN算法和凝聚算法。近年來，研究者对如何在大规模的在线社会网络中挖掘出社区结构进行了探索。燕飞、张铭等提出了综合行动者兴趣及网络拓扑结构的社区发现方法，即使用兴趣聚类的方法来发现用户的兴趣社区后，再考虑行动者的社会网络结构特征，主要运用社会网络权值计算、行动者间相关度计算和社区扩展，对兴趣社区进行扩展。Clauset、Newman等提出了一种基于贪婪算法思想的社团结构检测算法，CNM算法。该算法的计算采用堆数据结构计算和更新模块度。关于社区结构的检测算法其中有一种是标签传播算法（LPA），其基本思想是在算法开始时，给每个节点初始化一个不同的标签值，给每个节点指定一个标签，在算法进行中，节点将选择与最多邻居的所在社区改变标签。因此随着算法的进行，节点标签也不断变化，直到标签不再改变，则算法结束。
（作者单位：河北大学管理学院）
参考文献：
[1]Barabasi A-L，Albert R.Emergence of scaling in random networks[J].Science，1999.
[2]Adamic et al..A social network caught in the web[J]，First Monday，2003，8（6）：1-22.
[3]Liben-Nowell， D.， Novak， J.， Kumar， R.， Raghavan， P.， & Tomkins， A. （2005） Geographic routing in social networks. Proceedings of National Academy of Sciences， 102 （33） 11，623-11，628.
[4]Fu F， Chen X， Liu L， et a.l Socialdilemmas in an online socialnetwork： the structure and evolution of cooperation[J]. Phys-ics LettersA， 2007， 371（1-2）： 58-64.
[5]胡海波，汪小帆.在线社会网络的结构、演化及动力学研究[D].上海：上海交通大学，2010.
[6]F. Wang， Y. Moreno， Y. Sun， The structure of peer-to-peer social networks， Phys. Rev. E 73 （2006） 036123.
[7]燕飞，张铭，谭裕韦，唐建，邓志鸿.综合社会行动者兴趣和网络拓扑的社区发现方法[J].计算机研究与发展，2010（6）.