01-社会网络分析与算法研究

社会网络分析与算法研究主讲教师：高昇Cell：13120144593Email：[e-mail]：教三楼803-模式识别实验室助教：王岳Cell：15652961413Email：[e-mail]：教三楼803-模式识别实验室2《网络、群体与市场—揭示高度互联世界的行为原理与效应机制》大卫•伊斯利[美]/乔恩•克莱因伯格[美]著，李晓明等译，清华大学出版社，2011年10月《NetworksCrowdsandMarkets:ReasoningaboutaHighlyConnectedWorld》DavidEASLEYandJonKLEINBERG《复杂网络基础理论》郭世泽、陆哲明编著，科学出版社，2012年6月《链接：网络新科学》巴拉巴西[美]著，徐彬译，湖南科学技术出版社，2007年4月《社会网络分析：理论、方法与应用》林聚任、景天魁著，北京师范大学出版社，2009年8月参考资料期末成绩40%大作业or考试平时成绩40%小作业日常考勤20%考核方式研究对象：各种系统。。。5678美国航空网系统10城市公共交通系统各种复杂系统的共性是什么？11TheNetwork!一切系统的基础结构都是网络!SocialNetwork12InformationNetwork13Webpagehyperlinks14WorldWideWeb经济合作网络15大脑神经元网络169/11恐怖分子交流网络17不同领域的复杂网络社会网：社交网，演员合作网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网交通运输网：航线网，铁路网，公路网，自然河流网18中药方剂网虽然中药方剂的数量很大，但目前还没有统计用的数据库。不得不用手工进行统计，因此统计的数据量受到很大限制。选用了1536付药方，681种药物进行了统计。节点：药物，边：在一付方剂中药物的相互作用。方剂：药物、药物的相互作用构成的固定完全图局域网，同时也可以看作是节点（药物）的合作成果。各个完全图通过共用的节点（药物）架起桥梁，构成网络。网络由完全图连接而成，如图所示。19中药方剂网示意图点（药材），边（药材之间相互作用），局域网（方剂）20中国淮扬菜肴网21•节点-食料•边-菜肴中两种食料之间的相互作用•每道菜肴-局域网（完全图）•通过公共节点连接构成中国淮扬菜肴网。•329道菜肴，242个顶点（食品），1713条边。•类似于中药方剂网的讨论。江湖人物网络2223CommunicationNetworkViewNETWORKVIEWOFTHEWORLDTransportationPowerGridSocialBiologicalLanguage广义上来说，如果从图论角度理解网络，社会网络可以看作由一些具有独立特征的又与其他个体相互连接的节点的集合，每个个体可视为图中一个节点，节点间的相互连接视为图中的边，连线表示系统元素之间的相互作用。社会网络包括两个层面：作为其连接拓扑结构的图和作为其状态和功能的系统。社会网络分析是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础，反映结构与功能的关系。什么是社会网络？（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的，例如，上每天都不停地有页面和链接的产生和删除。静态结构的复杂性和结构动态演化的复杂性。例：神经系统由神经元互连形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）社会网络的特性（2）节点复杂性A）节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂多样性的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。或者社交网络中每个用户的兴趣偏好。B)关联引发的节点特性当关联失去时这类特性会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。社会网络的复杂性（3）复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。例如，电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。例如9/11事件。（4）网络分层结构的复杂性例如，行政管理网络是具有层结构的，多数网络都有节点的分层结构，不同分层之间的相互作用会对整体网络的结构和功能产生影响。社会网络的复杂性1）复杂网络模型分析典型的复杂网络：随机网、小世界网络、无标度网络等.2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。3）网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。4）社会网络的动力学（信息扩散机制）信息传播动力学、网络演化动力学、网络混沌动力学。5）网络的复杂结构分析社团检测、层次结构、节点分类结构等。6）社会网络建模机理建模、数据建模和实际系统的复杂网络建模。7）网络链接分析网络中链接预测、链接分类、节点排序等。社会网络分析的研究内容狭义上来说，社会网络是指由个人或团体以及他们之间存在的各种关系所组成的社交网络。这些网络关系包括:好友关系、关注关系、博客间的评论关系、标签系统(taggingsystems)中用户间的协作标签关系等。在过去的半个世纪，社交人际网络一直是社会学、社会心理学和人类学的活跃的研究领域。如今，社会网络涵盖了社会和技术性的网络，以及具有内在社会化结构的信息系统。特别是随着Web2.0的发展，出现了很多基于Web的社会网络数据，包括在线社区(如Facebook、人人网、校内网等)、微博、微信、文献发表数据库等。社会网络分析主要对社会化网络中的关系进行分析，得到个人或社团(community)的信息。因此，社会网络分析可以用于检测可信任的重要用户、好友预测、提高网络搜索性能、商品推荐等。社会网络分析（狭义）社会网络分析是一门社会学、信息学、计算机科学、物理学、、生物学、统计学等多学科交叉的新兴领域，涉及了网络建模、数据挖掘、机器学习、信息抽取与检索、统计分析等不同领域。社会网络分析的发展是建立在：组织社会学与社会测量学复杂网络理论机器学习算法与模型社会网络分析的研究方法社会网络分析作为一种独特的理论和研究方法从20世纪60年代兴起、70年代快速发展、80年代成熟到90年代长盛不衰,历时近40年。从20世纪70年代初期至今占据着欧美社会学特别是美国社会学主流地位的则是社会网络分析，提出了从“经济人”到“社会人”的转变。其领军人物包括:伯特(RonaldBurt)、格兰诺维特(MarkGranoveter）、诺科(DavidKnoke)、马斯登(PeterMarsden)、维尔曼(BarryWellman)、怀特(HarrisonWhite)等学者。社会网络分析提出了一系列指导着社会网络研究的概念、命题、基本原理及其相关的理论，使社会学对于社会结构的研究面目一新。社会网络分析形成了得到大规模的经验研究支持的一致的特征和原理。在社会关系的层次上将微观社会网和宏观的社会结构连结起来.社会网络分析的发展历史I定量研究：从数学领域的图论发展到系统科学领域的复杂网络理论，再到社会科学领域的社会网络分析。哥尼斯堡七桥问题社会网络分析的发展历史IIEuler（1707~1783），瑞士数学家，图论之父一笔画问题1736年，七桥游戏34随机图理论20世纪60年代，由两位匈牙利数学家Erdǒs和Rényi建立的随机图理论（randomgraphtheory）被公认为是在数学上开创了复杂网络理论的系统性研究。Erdǒs和Rényi的最重要的发现是：ER随机图的许多重要性质都是突然涌现的。也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？20世纪60年代美国哈佛大学的社会心理学家斯坦利•米尔格伦(StanleyMilgram)通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离”：平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度。30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。社会网络分析的发展历史II36米尔格伦的实验过程是：他计划通过人传人的送信方式来统计人与人之间的联系。首先把信交给志愿者A，告诉他信最终要送给收信人S。如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的朋友圈里B是最可能认识S的。但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，……，就这样一步步最后信终于到达S那里。这样就从A到B到C到……最后到S连成了一个链。斯坦利•米尔格伦就是通过对这个链做了统计后做出了六度分离的结论。然而在这个实验中，实际上只有三分之一的信送到了收信人那里，因此实验的完成率很低。小世界实验：“六度分离”37小世界实验—Bacon数为了检验“六度分离”的正确性，美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就可以知道这个演员的Bacon数。目前比如输入StephenChow（周星驰）就可以得到这样的结果：周星驰在1991年的《豪门夜宴(Haomenyeyan)》中与洪金宝(SammoHungKam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的《死亡的游戏（GameofDeath）》中与ColleenCamp合作；ColleenCamp在去年的电影《Trapped》中与KevinBacon合作。这样周星驰的Bacon数为3。对78万个演员所做的统大Bacon数仅仅为8，平均Bacon数仅为2.948。38有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：（1）一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》（CollectiveDynamicsof‘Small-World’Networks）的文章，这篇文章揭示了复杂网络的小世界特征，并建立了相应的模型以阐述这些特性的产生机理。RegularNetRandomGraphLargeLandCWS‘Small-World’ModelSmallLandCStartwithorder:BeginwithaNNnet.,whereeachnodeisadjacenttoitsKneighbornodes.Randomization:Randomlyrewireeachedgeofthenetworkwithprobabilityp(shiftingoneendoftheconnectiontoanewnodechosenatrandom)WS‘Small-World’Model4