科普文:从人人网看网络科学(Network Science)的X个经典问题

http://blog.renren.com/share/270937572/16694767796?from=0101010202&ref=hotnewsfeed&sfet=102&fin=3&fid=24297752024&ff_id=270937572&platform=0&expose_time=1386225841

科普文:从人人网看网络科学(Network Science)的X个经典问题作者: 邓岳

    长文,写了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]。

说着简单,给你一个网络看着好像也简单,上图左边三个红点之间就明显有一个社团,但找着可就难了。社团发现的方法流派很多,我之前发的一篇日志列了主流的一些方法。

在社团发现中,还有一大类方法是处理重叠社团(overlapping community)。所谓重叠社团,指节点可以属于多于一个的社团。比如考虑你的好友,高中同学可以聚成一个社团,本科同学可以聚成一个社团,而你既属于高中同学的社团,也属于本科同学的社团。

需要注意的是:在网络中(尤其是生物网络),一个社团/模块未必会表现出连接稠密的性质。

==================================

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次方),对于大网络效率太低(社会网络甚至可以得到千万甚至亿级节点)。

经典的Brandes算法对于无权图(认为每条边的长度均为1)的复杂度可以到O(节点数*边数)。

最后简单说说接近中心性

接近中心性的基本思想:如果一个人能很容易的联系到其他人,那么TA就是中心的。即TA到其他所以人的距离比较短。在定义时采用网络中两点间最短距离的概念(Dijkstra算法没忘吧),定义如下:

节点i的接近中心性 = ( n-1 ) / ( i到网络中其他点的最短距离的和 )。其中n为网络中节点个数,n-1即为除了i之外的总节点数目。

接近中心性的应用在后面会说。

==================================

4、复杂网络的一些拓扑特性

 (1)小世界(Small World)

常听到的一个概念,社交网络中的“六度分隔”原理(Six Degree Separation)就是小世界现象的一个表现。其核心是网络中任意两点的平均最短距离低。

从人人网也能看出,它是很稀疏的网络,整个网络几千万个节点,每个节点的邻居一般就是几十到几百个。任意选出两个节点,它们之间有连边的可能性很低,但它们的最短路径一般很短(从Facebook数据来看,网络中任意两点的平均最短路径约为4)。

那么,如何能把一个规则网络变成满足小世界特性的网络呢?可以通过随机重连边的方式,看下图(a),原版的网络(深灰色边)是一个规则网络,每个节点的度均为4(连接它左右的4个节点)。通过随机把一些边重连(黑色边),会产生一些“捷径”(short cut),能迅速降低网络中各点的平均最短距离。

 (2)无标度(Scale-free)

整个人人网里,如果把每个节点的度(好友个数)做一个统计,会是什么样的分布呢?

可以想象,度数高的节点是很少的,度数低的节点占绝大多数

无标度网络各节点之间的连接状况(度数)具有严重的不均匀分布性:网络中少数Hub节点拥有极其多的连接,而大多数节点只有很少量的连接。具体来说,节点的度分布符合幂率分布(power law)。所谓无标度,指的是少数高度数的节点的度数非常高,高到爆表。

那么,如何能生成一个无标度网络?经典的BA模型是这样说的:当有新的点加入到网络中时,它会根据概率和网络中的其他点相连,新的点X和老的点Y相连的概率正比于Y的度,即新的节点更倾向于连接到原本度数高的节点(Hub),也称为“优先连接(preferential attachment)”特性,或者叫“富者更富(rich get richer)”或者“马太效应(Matthew effect)”。通过反复添加新节点,就能构建出一个无标度网络。

这个用人人举例不是非常形象,我换用微博举例。一个新注册的微博用户会关注哪些微博呢?有很大可能是关注那些已成名的“大V”(手哥、李开复……)。“大V”即为Hub节点,新节点偏向于和这些Hub相连。如果没有突发情况,“大V”的粉丝增加速度始终会快过普通用户,即“富者更富”。

幂率分布是个复杂网络研究中的大神级概念,感兴趣的同学务必自己多查资料。这里举个简单例子:你一天要发很多短信,我们考虑一下两条短信之间的相隔时间。首先,间隔肯定不是固定的(比如你每小时发一条短信),显然是随机的。那这个随机的时间是否符合某种概率分布?直观想可能是高斯分布(钟形),大多数短信间隔时间差不多(比如每小时左右发一条),但少数短信间隔时间很长(半天也没发一条)或很短(1小时发了3条)。但实际上,发短信存在着“爆发”现象,某些情况下你可能10分钟就发了10条(联系其他同学吃饭,或者通知),而有时可能10小时也没有发一条(睡觉)。而这种爆发在高斯分布中是不可能出现的,感兴趣的同学可看巴拉巴西的《爆发》

 (3)Giant Component

一个规模很大的网络中,可能存在多于一个的连通分支/连通分量(Connected Component),即网络中并非所有节点都连通。但是在真实网络中通常存在一个规模很大的连通分支(即Giant Component)会包含网络中大多数的节点(比如超过80%的节点)。

如果一个人刚注册人人,还没加好友,那他就是一个孤立点(没有和任何其他点相连)。而一旦有了好友,就不再是孤立点。如果某个学校规定学生在人人只能加本校好友,不能有外校好友,那么这个学校的学生也会构成一个小的独立的连通分支。不过可以想到,人人里绝大多数的同学都处在一个超大的连通分支中,真正孤立的节点或小的连通分支所占用户数是很少的。

Facebook的数据显示约99.7%的用户处在一个超大的Giant Component中。

==================================

5、高影响力节点(high influential nodes)/传播(spread)

识别网络中的高影响力节点(leader)有什么用?拿信息传播来说,如果你希望你的信息能迅速在网络中传播,那你就要考虑选择通过高影响力节点来传播信息。

早期的研究结果认为网络中的高度数(Hub节点)或高介数的节点是传播中最有影响力的节点,这是因为Hubs节点拥有更多的人际关系,而高介数的节点有更多的最短路径通过。

高度数节点的例子:你把一卡通丢了,在人人发了一个寻物状态,然后@了一些公共主页(西电小喇叭、西电睿思、在西电……)。因为你觉得这些公共主页因为好友比较多(degree高,属于网络中的Hub),能更有效地把你的信息扩散出去。

高介数节点的例子:你班里的同学A和计算机学院的同学B是情侣。你的班级想和计算机学院合办一个讲座,班长发状态圈了A,A分享给B,B的分享就让很多计算机学院的同学看到了这个信息。尽管A、B两人的好友(degree)未必很高,但A、B算是软件学院、计算机学院两个社团之间的“桥梁”(请回看2中的图中的红点),介数中心性比较高(请回看3),也在信息传播中扮演重要角色。

上面两个例子都很好理解,很符合直观思维,但说的就是对的么?

从直观来想,对于一个网络,应该是靠近网络“中心”的节点具有较高的传播能力。如上图中间红圈中的4个点,可以很迅速的把信息传播到绿圈和蓝圈。

对于上图中的黄色点,虽然其度数很高,但由于并不处于网络“中心”,传播能力显然不如红圈中的4个点。例如:黄色点要把信息传给最下方的红点(位于蓝圈),就需要先传到红圈中,再向下传到绿圈中的红点,最后才能传到蓝圈。

上例和之前认为”高度数节点的影响力高“存在着明显矛盾。“度数高的点影响力高”好理解且好计算,因为网络中一个节点的度数,就是其邻居个数,不管是用邻接矩阵还是邻接表存储,都很容易求得。但“靠近中心”这是个很模糊的说法,和网络的布局(layout)有关系。如果一个网络已经画出来了,我们一眼就能看出所谓的“中心”在哪里。但如果是采用另一个画法,比如你人为把上图中的蓝色点拖到网络外围,那它也就不在中心了。

说到这里,就产生了一个新问题:如何形式化的(用数学手段)确定网络的“中心”?

直观的看,可以用上面的“接近中心性”来计算。位于网络中心的节点,和其他节点的最短距离都比较小;而位于网络边缘的节点,和很多节点(位于网络另一侧的节点)的最短距离都比较大。但是,接近中心性需要计算网络中任意两点间的最短距离,计算量很大。

也有研究者提出利用图论中的概念“K-Shell”来进行:

1、首先删除网络中所有度为1的节点。删完以后检查,原来某些度大于1的节点会变成度为1的,就继续删,删完再检查,再删……直到没有度为1的节点为止。最终,认为刚才所有删掉的的节点属于第一层,即ks=1的节点(上图外围蓝色圈);

2、现在网络中肯定没有度为1的节点了(都删掉了),那就开始删除度为2的节点(和上一步方法一致)。这次删掉的就是ks=2的节点(上图绿圈);

3、依此类推,接着删度为3的节点,然后是度为4的节点……最终网络删干净了,网络中所有的点都被分配了一个ks值。

实验研究表明,对于单个传播源的情形(你只圈一个公共主页让其帮你转发),Hubs节点或者高介数的节点不一定是最有影响力的节点,而通过K-shell分解分析确定的网络核心节点(K-shell值大的节点)才是最有影响力的节点;对于多传播源情况下(你圈了多个公共主页来帮你转发),传播的规模很大程度依赖于初始传播源之间的距离,此时选择多个Hub节点是比较有效的。

==================================

6、网络的比对(alignment)、去匿名化(de-anonymization)

我们一般不止用一个SNS(比如同时在用QQ和人人),那多个SNS网络存在着部分一致(比如你宿舍8个人在人人上互相加了好友,在QQ上也互相是好友)。网络比对的目的就是寻找两个网络中的节点的对应关系。

如上图(图片来自http://botao.hu/works/research/de-anonymizingsocialnetworks)所示,比如说左边网络是人人,右边是QQ。根据两个网络极其中节点的拓扑特征,我们把两个网络中的节点进行映射(虚线),即虚线相连的两个点,是同一个实体(人)。

通过网络比对,得到两个网络间节点映射,有啥用?

一个应用是“去匿名化”,顾名思义就是搞清楚网络中的匿名用户到底是谁。比如说公安机关发现人人网里一个名为wurht的用户在疯狂造谣(左图左下角翠绿节点),但人人中其注册所用信息是假的。通过网络比对,可以知道人人中的wurht用户对应着QQ中的wurh用户,而通过腾讯可以查到其身份,自然也就知道了人人中wurht的真实身份。

需要注意的是,网络比对可以仅利用拓扑特征,也可整合更多的特征(比如节点的某些个人信息)。比如腾讯的圈子中的“智能备注”功能,会根据一个用户的好友对其的备注,来推断其真实身份(根据腾讯官方说明:如果圈子内有半数以上的好友对您设置相同的QQ备注名,这个备注名将默认成为您在圈子内展现的名称。)。这和标签传播(Label Propagation,用已标记节点的标签信息去预测未标记节点的标签信息)的思想有些类似。

==================================

7、动态网络(Dynamic Networks)/演化(Evolution)

这里的动态网络主要指网络在不同时间点的变化。拿人人网为例,如果你每月的一号把人人网里你好友的数据储存一次(保存你的好友、好友的好友之间的连边关系),连续存上一年,就形成了由12个静态网络组成的动态网络。在这12个静态网络中,节点和边可能都不一样(注意在前面链路预测研究中,节点是不变的)。

我们把这12个静态网络依次来看,看每个月和下一个月之间的差异。可以用前面讲的社团发现的方法,对每个静态网络进行聚类,然后研究相邻两个月之间社团的变化情况。可以定义如下六种相邻时刻间的变化:

(1)Growth:同一个社团,在相邻时刻出现了增长(如节点变多了)。和Growth相对的就是Contraction。

(2)Merging:t时刻的两个社团,在t+1时刻合并成了一个社团。和Merging相对的就是Splitting。

(3)Birth:t+1时刻新出现了一个社团(该社团在t时刻不存在)。和Birth相对的就是Death。

比如在1月1号时,软件学院的小帅(男)和人文学院的小美(女)的两个宿舍,各自构成了一个社团(比如是8个节点的完全图)。但由于这两个宿舍的人互相之间并不认识,所以两个社团间的连边很少。在1月中旬,小帅和小美成为了情侣,两个宿舍的人也开始互相认识,大部分同学之间也加了人人好友。在2月1号,由于这两个宿舍原先构成的社团之间多了很多连边,这两个社团就合成了一个大的社团(16个节点的近似完全图)。这就是上图的Merging。又过了几个月,俩人又分手了,两个宿舍的人也纷纷取消删了之间的好友关系,一个大社团又回到了最早的两个社团,即为Splitting。

 

【未完待续】

==================================

网络科学自学资料

一、书

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章。

3、Social and Economic Networks: Models and Analysis,斯坦福,2014.1开课(来自文后留言)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s