social network

Wang Cheng-Jun edited this page Dec 19, 2016 · 1 revision

计算传播学是计算社会科学的重要分支。它主要关注人类传播行为的可计算性基础,以传播网络分析、传播文本挖掘、数据科学等为主要分析工具,(以非介入地方式)大规模地收集并分析人类传播行为数据,挖掘人类传播行为背后的模式和法则,分析模式背后的生成机制与基本原理,可以被广泛地应用于数据新闻和计算广告等场景,注重编程训练、数学建模、可计算思维。

Clone this wiki locally

Assortative mixing in networks

众所周知,节点的度是网络最基本的结构属性。一个网络中度较大的节点倾向于和其他度较大的节点相连接,这一现象被称为Assortative mixing(相称混合)。Newman(2002)研究了这一现象,他给出了一种模型,该模型显示,这种性质会对整个网络系统的行为(behaviour)产生显著的影响,比如,当网络具有这样的性质时,它会变得更容易扩散(percolate),此外,当某个节点被移除时,网络有更强的鲁棒性。

首先建立一个无向图G,有N个节点,M条边,节点的度分布为 <math>p_{k}</math>,<math>p_{k}</math>表示从G中随机选取一个点的度为k的可能性。现在考虑从G中随机选取一条边,则它一个端点的度分布就不符合<math>p_{k}</math>,而会偏向于有大的度值,因为与度小的节点相比,更多的边会和度较大的节点相连。因此这样的点的度分布与<math>p_{k}</math>成正比,记为<math>kp_{k}</math>。定义<math>e_{jk}</math>为连接了度为j和度为k的节点的那些边,<math>q_k</math>为节点的remaining degree(excess degree)[1]的分布。<math>e_{jk}</math>与<math>q_k</math>有如下关系

<math>\sum_{jk}e_{jk}=1 \quad \sum_je_{jk}=q_k</math>

由文献[2]可以得到

<math>q_k=\frac{(k+1)p_{k+1}}{\sum_jjp_j}</math>

事实上,<math>\sum_jjp_j</math>就是网络中节点度的平均值。

由此可以定义出图G的相称系数(assortative coefficient)

<math>r=\frac{\sum_{jk}jk(e_{jk}-q_jq_k)}{\sigma_q^2}</math>

其中,<math>\sigma_q</math>是<math>q_k</math>的标准差。可以发现,r的值在[-1,1]之间,r=1表示perfect assoratativity,r=-1时表示perfect disassortativity。

相应的,对于一个有向图而言

<math>r=\frac{\sum_{jk}jk(e_{jk}-q^{in}_jq^{out}_k)}{\sigma_{in}\sigma_{out}}</math>

此时,<math>e_{jk}</math>表示随机选取一条有向边,其起点度为k,终点度为j的概率

为了便于计算,将上式改写为

<math>r=\frac{\sum_ij_ik_i-M^{-1}\sum_ij_i\sum_{i^`}k_{i^`}}{\sqrt{[\sum_ij_i^2-M^{-1}(\sum_ij_i)^2][\sum_ik_i^2-M^{-1}(\sum_ik_i)^2]}}</math>

此时,<math>j_i</math>和<math>k_i</math>表示第i条边的终点的excess in-degree和起点的excess out-degree,M为边的总数。

r的统计误差用<math>\sigma_r^2</math>来衡量<math>\sigma_r^2=\sum_{i=1}^M(r_i-r)^2</math>

[1] M.E.J. Newman, Phys. Rev. Lett. 89, 208701 (2002)". the remaining degree means the number of edges leaving the vertex other than the one we arrived along.

[2] M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. E 64, 026118 !2001". Random Graphs with Arbitrary Degree Distributions and Their Applications