|
长文，写了N个小时写完的。你肯定能看懂，所以希望你能看完，没看完就分享/点赞没有意义。有图有超链接，不建议用手机看。相关内容我想应该可以弄成一个小项目加到某门课中。
网络科学是这两年非常热门的研究方向，本文用人人网举几个简单例子，说明一下网络科学中的一些经典问题。 社交网络（社会网络）是典型的的复杂网络，有小世界、模块化、无标度等特性。网络中节点（node）代表人，连边（edge/link）代表两个人是好友关系。下图是示意图，红点的意思后面说。 1、链路预测（Link Prediction）： 链路预测是预测网络中“不存在但应该存在的边”或“现在不存在但以后可能存在的边”。对应到人人网，前者是说俩人实际上认识，但在人人里没加好友（人人数据相比真实来说缺失了一部分）。后者说俩人现在不认识，但有成为朋友的潜质（比如有共同兴趣等）。本文以前者为例进行说明，对应人人里的好友推荐。 人人的好友推荐大体会给你推荐和你的共同好友多的人。潜台词：两人的共同好友数越多，他们认识的可能性也越高。
（1）最简单的指标（Common Neighbors，CN） 某人的好友即为其在网络中的neighbors（有边相连的node），共同好友即为两人好友的交集。 CN为两人共同好友的个数，直观感觉CN越大，此二人是好友的可能性越大。 CN(x,y)=|N(x)∩N(y)| N(x)为节点x的所有邻居（计算原因也可以加上x自己） 直观感觉基本没有问题，但CN会让好友多的人“占便宜”。举一个例子：你的好友A和你在人人里还没加好友，A不太玩人人，在人人里只有2个好友，这两个人你都认识，你和A的CN=2。而你的辅导员和你的CN=50（你班里很多同学都和辅导员是人人好友）。如果人人按CN从高到低推荐，那很可能推荐辅导员，很可能不会给你推荐A。 （2）改进指标（Jaccard index） 从上得知，好友多的人沾光，应进行修正（惩罚），Jaccard系数定义如下： Jaccard(x,y)=|N(x)∩N(y)| / |N(x)∪N(y)| 当然，改进方法还有很多，大体都是惩罚度数高的节点。比如如除以 k(x)+k(y) 或 k(x)*k(y) 等。k(x)为网络中节点的度，相当于邻居个数。 你会发现人人也会给你推荐只有两三个共同好友的朋友，就是这个原因。
代码如何实现？ 数据结构里学过图（graph），图就是网络（network）。图的存储可以有邻接矩阵、邻接表等。 邻接矩阵：方阵，行和列都是网络里所有节点，矩阵元素0代表两节点有连边，1代表无连边。 邻接表：每行为一个节点，后面跟链表，链起来它的所有邻居。适合存储稀疏网络。
先说邻接矩阵，节点x所在行/列所有为1的元素对应的列/行即为x的好友（邻居），同理求y的好友，即可进行计算。 邻接表更简单，x所在行的链表就是x的好友。
我刚注册人人，一个好友都没有，何谈共同好友？ 这是链路预测的一个经典挑战：冷启动（Cold Start）。即对新用户（信息很少）的推荐。 人人网当然不会在共同好友一棵树上吊死，对于新用户，它会根据用户填写的资料进行推荐。如推荐和你同年入学同所学校，或同年龄家乡在相同城市的人等。
这里还有问题大家可以考虑：推荐的都是目前和你没加好友的人，但整个人人里和你不是好友的有几千万人，总不能给这些人全都和你算一个共同好友数目，然后排序推荐。如何能圈定一个大致的范围？ ================================== 2、社团发现（Community Detection）
社团发现是网络科学里另一个火爆问题。社团指网络中比较稠密（dense）的部分，就是连边紧密的几个人组成的一个小团体。社团具有“内紧外松”的性质，即社团内部连边稠密，而和社团外部的点连边相对稀疏。 比如你和宿舍的7个人，一共8个人，每两个人都加了人人好友。在网络里就是8个两两相连的点，构成一个大小为8的完全图（complete graph/clique，图中任两点间都有连边）。 假设有N个点，若最极端情况两两相连构成完全图，共有 N(N-1)/2条边。这是N个点之间边数的上线。 可以用简单的方法衡量网络中的一个子图（M条边，N个节点）的稠密程度：dense=M/[N(N-1)/2]，显然dense∈[0,1]。 说着简单，给你一个网络看着好像也简单，上图左边三个红点之间就明显有一个社团，但找着可就难了。社团发现的方法流派很多，我之前发的一篇日志列了主流的一些方法。 ================================== 3、中心性（Centrality） 复杂网络研究中的“中心性”包括：度中心性（Degree Centrality）、介数中心性（Betweenness Centrality）、紧密中心性 (Closeness Centrality) 等多种度量方式。 先简单介绍一下度中心性。 度中心性就是节点的度（节点邻居个数），度数高的节点一般叫做Hub节点。 度中心性说明了什么？ 人人网络中度数高的节点就是好友多，微博网络中度数高的节点就是粉丝多。Hub节点对于网络信息扩散有很大帮助。 度中心性有什么应用？ 我想在微博上打广告，只要在李开复、留几手这种Hub节点上投放广告，很快很多用户就能看到。 对于传染病传播来说，Hub节点因为能接触到多人，因此一旦得病很容易传染给周边人群。 对于铁路网络（节点是火车站，边表示两火车站间存在铁路），像徐州、郑州这种交通枢纽城市即为Hub节点。有意识的在全国不同地区设置Hub节点，可以优化车次中转。
然后稍详细说一下介数中心性。 介数中心性用来衡量网络中节点和边的重要性，和最短路径紧密相关。 节点s的介数中心性 = 网络中任意两点间的最短路径中通过s的最短路径条数 / 网络中任意两点间的最短路径数 边e的介数中心性 = 网络中任意两点间的最短路径中通过e的最短路径条数 / 网络中任意两点间的最短路径数 对于连通网络，上式分母即为 N(N-1)/2。分子是看这么多条最短路径中，有多少条经过s。 显然 节点的介数中心性∈[0,1]。对于边缘节点（叶子），介数中心性为0；对于星型网络的中央节点，因为所有的最短路径都经过它，所以它的介数中心性为1。 介数中心性说明了什么？ 介数中心性高的节点/边一般处于网络的“交通要道”，起到信息传输桥梁的作用，通常处于两个社团之间。上图中红色的点都是介数中心性较高的点。 介数中心性有什么应用？ 对于网络攻击而言，希望击毁尽可能少的节点就让网络瘫痪，则可以选择介数中心性高的节点进行攻击。若把上图中6个介数中心性高的节点移除（同时删除红点连接的边），网络就会被分割成多个碎片。 对于上面说的社团发现而言，其实也可以利用移除介数中心性高的节点，让网络自然分成内紧外松的几部分。 介数中心性怎么算？ 算法很简单，先用Floyd-Warshall算法计算网络中任意两点的最短路径算法，作为分母。分子就是通过某个顶点或某条边的最短路径。但是，Floyd算法就复杂度O(节点数的3次方)，对于大网络效率太低（社会网络甚至可以得到千万甚至亿级节点，如Facebook）。 经典的Brandes算法对于无权图（认为每条边的长度均为1）的复杂度可以到O(节点数*边数)。 ================================== 4、复杂网络（Complex Network）的一些拓扑特性 （1）小世界（Small World） 常听到的一个概念，社交网络中的“六度分隔”原理（Six Degree Separation）就是小世界现象的一个表现。其核心是网络中任意两点的平均最短距离低。 从人人网也能看出，它是很稀疏的网络，整个网络几千万个节点，每个节点的邻居一般就是几十到几百个。任意选出两个节点，它们之间有连边的可能性很低，但它们的最短路径一般很短（从Facebook数据来看，网络中任意两点的平均最短路径约为4）。 （2）无标度（Scale-free） 整个人人网里，如果把每个节点的度（好友个数）做一个统计，会是什么样的分布呢？ 可以想象，度数高的节点是很少的，度数低的节点占绝大多数。 无标度网络各节点之间的连接状况（度数）具有严重的不均匀分布性：网络中少数Hub节点拥有极其多的连接，而大多数节点只有很少量的连接。
================================== 5、高影响力节点（high influential nodes） 识别网络中的高影响力节点（leader）有什么用？拿信息传播来说，如果你希望你的信息能迅速在网络中传播，那你就要考虑选择通过高影响力节点来传播信息。 早期的研究结果认为网络中的高度数（Hub节点）或高介数的节点是传播中最有影响力的节点，这是因为Hubs节点拥有更多的人际关系，而高介数的节点有更多的最短路径通过。 高度数节点的例子：你把一卡通丢了，在人人发了一个寻物状态，然后@了一些公共主页（西电小喇叭、西电睿思、在西电……）。因为你觉得这些公共主页因为好友比较多（degree高，属于网络中的Hub），能更有效地把你的信息扩散出去。 高介数节点的例子：你班里的同学A和计算机学院的同学B是情侣。你的班级想和计算机学院合办一个讲座，班长发状态圈了A，A分享给B，B的分享就让很多计算机学院的同学看到了这个信息。尽管A、B两人的好友（degree）未必很高，但A、B算是软件学院、计算机学院两个社团之间的“桥梁”（请回看2中的图中的红点），介数中心性比较高（请回看3），也在信息传播中扮演重要角色。 上面两个例子都很好理解，很符合直观思维，但说的就是对的么？ 从直观来想，对于一个网络，应该是靠近网络“中心”的节点具有较高的传播能力。如上图中间红圈中的4个点，可以很迅速的把信息传播到绿圈和蓝圈。 对于上图中的黄色点，虽然其度数很高，但由于并不处于网络“中心”，传播能力显然不如红圈中的4个点。例如：黄色点要把信息传给最下方的红点（位于蓝圈），就需要先传到红圈中，再向下传到绿圈中的红点，最后才能传到蓝圈。 上例和之前认为”高度数节点的影响力高“存在着明显矛盾。“度数高的点影响力高”好理解且好计算，因为网络中一个节点的度数，就是其邻居个数，不管是用邻接矩阵还是邻接表存储，都很容易求得。但“靠近中心”这是个很模糊的说法，和网络的布局（layout）有关系。如果一个网络已经画出来了，我们一眼就能看出所谓的“中心”在哪里。但如果是采用另一个画法，比如你人为把上图中的蓝色点拖到网络外围，那它也就不在中心了。 说到这里，就产生了另一个问题：如何形式化的（用数学手段）确定网络的“中心”。 【未完待续】 ================================== 6、网络的比对（alignment）、去匿名化（de-anonymization） 【未完待续】 ================================== 网络科学自学资料 一、书 1、《网络科学导论》、《链路预测》、《网络科学》 、《Network Science》 入门且全面，正统的Network Science 2、《推荐系统实践》、《推荐系统》 主流的Web应用里都有推荐系统，算是网络科学的主要应用方向 3、《网络、群体与市场》 也是入门书，结合经济学、社会学、计算与信息科学以及应用数学的有关概念与方法，考察网络行为原理及其效应。 4、《链接》 早期经典著作 二、公开课 1、Social Network Analysis 2013.3开课时我全程跟下来并拿到了成绩。2013.10再次开课。强烈建议英文差不多的10级不考研同学10月跟一下这个。 2、网络、群体与市场 中文公开课，在Coursera也有。对软件方向的同学，建议重点看一下课程的第2、3、9、11、13~17章。 |
|
|
