#!/usr/bin/env python
# coding: utf-8
# # 网络科学基础
# ——以意见领袖挖掘算法为例
#
# 张子柯 教授
# zhangzike@gmail.com
# 阿里巴巴复杂科学研究中心
# # 二十一世纪科学研究的特点
# 二十世纪，科学研究的特点是分析的方法，还原论的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分析），……
#
# 二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法。普列高津的耗散结构理论，哈肯的协同学，混沌和复杂系统理论，系统生物学 … …
#
# 当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后，研究“如何组合”的问题。这种方法导致复杂网络结构的研究。
# # 什么是系统？
# 系统：集合（具体元素）+ 结构+功能。
# # 系统的结构是什么？
#
# - 一切系统的基础结构都是网络；
# - 一切系统的核心结构都是逻辑网络；
# - 复杂系统的结构就是复杂网络。
#
# **复杂网络**是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；
# **复杂网络**在刻画复杂性方面的重要性是由于结构决定功能的。
# **复杂网络**是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。
# # 网络系统的复杂性
# ## 1. 结构复杂性
# 网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的，例如，WWW上每天都不停地有页面和链接的产生和删除。
# ## 2. 节点复杂性
# ### 2.1 节点的独立或固有特性
# 网络中的节点可能是具有分岔和混沌等复杂非线 性行为的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。
# ### 2.2 关联引发的节点特性
# 当关联失去时这类特性会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。
# ## 3. 复杂网络之间相互影响的复杂性
# 实际的复杂网络会受到各种各样因素的影响和作用。例如，电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。
# ## 4. 网络分层结构的复杂性
# 例如，行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多网络中没有意识到是一种造成复杂性的重要结构。
# ### 有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：
#
# 一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》（Collective Dynamics of ‘Small-World’ Networks）的文章；
#
# 另一篇是美国Notre Dame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》（Emergence of Scaling in Random Networks）的文章。
#
# 这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。
#
# # 复杂网络研究内容
# ## 1. 复杂网络模型
# 典型的复杂网络：随机网、小世界网、无标度网等；
# ## 2. 网络的统计量及与网络结构的相关性
# 度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。
# ## 3. 复杂网络性质与结构的关系
# 同步性、鲁棒性和稳定性与网络结构的关系。
# ## 4. 复杂网络的动力学
# 信息传播动力学、网络演化动力学、网络混沌动力学。
# ## 5. 复杂网络的复杂结构
# 社团结构、层次结构、节点分类结构等。
# ## 6. 网络控制
# 关键节点控制、主参数控制和控制的稳定性和有效性。
# ## 7. 复杂网络建模
# 机理建模、数据建模和实际系统的复杂网络正向与逆向建模。
# ## 8. 复杂逻辑网络
# 逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。
#
# # 二十一世纪的科学：复杂网络研究
# ## 突破性进展的主要原因
#
#
# 1. 越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。
#
# 2. 学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。
#
# 3. 以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。
#
# # 复杂网络中的节本概念
# ## 度
# 节点$i$的度$k_i$定义为与该节点连接的其他节点的数目。
#
# **直观上看，一个节点的度越大就意味着这个节点在某种意义上越重要.**
#
# ## 聚类系数
# ### 1. 节点的聚类系数（簇系数）
# 在简单图中，设节点$v$的邻集为$N(v)$, $|N(v)|=k_i$，则节点$v$的聚类系数定义为这$k_i$个节点之间存在边数$E_i$与总的可能边数$k_i(k_i-1)/2$之比，即：$C_i=2E_i/k_i(k_i-1)$。 **该值表明了节点$v$的邻点间关系的密切程度。**
#
# ### 2. 网络的聚类系数$C$
# 所有节点$i$的聚类系数$C_i$的平均值。$C=0$网络中所有节点都是孤立点，$C=1$网络中任意节点间都有边相连。
# **网络节点间联系的密切程度, 体现网络的凝聚力。**
# # 介数
# **点介数**：网络中通过该节点的最短路径的条数。
#
# **边介数**：网络中通过该边的最短路径的条数。
#
# 反映了节点或边的作用和影响力。如果一对节点间共有$B$条不同的最短路径，其中有$b$条经过节点$i$，那么节点$i$对这对节点的介数的贡献为$b/B$。把节点$i$对所有节点对的贡献累加起来再除以节点对总数，就可得到节点i的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例。
#
# **介数越大，说明经过该节点（边）的最短路径越多。在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞。
# 研究表明，节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。**
#
# # 核数
#
# **一个图的k-核**：反复去掉图中度小于等于$k$的节点后，所剩余的子图。
#
# 若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k，例：所有度为1的节点的核数必为0
#
# 节点核数中的最大值称为**网络图的核数**
#
# **节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小。例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为0**
#
# # 问题
#
# 目前刻划复杂网络的统计量有很多，例：**聚类系数，平均路径长度，平均度，介数，核数**等。
# * 能不能用一个或尽可能少的统计量来综合刻划复杂网络的结构呢？
# * 用多少相互独立的统计量刻画复杂网络的结构是完备的？
#
# # 复杂网络实例
#
# 
# 
# 
# 
# # 通讯网络vs经济水平
# 
# 
# 
# 
# # PageRank算法 -基于动力学的意见领袖识别
# ## 1. 算法来源
# ## 2. 算法原理
# ## 3. 算法实现
# ## 4. 算法演示
# # 算法来源
#
# 这个要从搜索引擎的发展讲起。最早的搜索引擎采用的是 分类目录的方法，即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用的这种方法。
# 后来网页越来越多，人工分类已经不现实了。搜索引擎进入了文本检索的时代，即计算用户查询关键词与网页内容的相关程度来返回搜索结果。这种方法突破了数量的限制，但是搜索结果不是很好。因为总有某些网页来回地倒腾某些关键词使自己的搜索排名靠前。
# 后来，谷歌的两位创始人，佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了，非常简单：
#
# **如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高**
#
# **如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高**
#
# 
# # 算法原理
#
# $PageRank$算法总的来说就是预先给每个网页一个$PR$值，由于$PR$值物理意义上为一个网页被访问概率，所以一般是$1/N$, 其中$N$为网页总数。另外，一般情况下，所有网页的$PR$值的总和为$1$。如果不为$1$的话也不是不行，最后算出来的不同网页之间$PR$值的大小关系仍然是正确的，只是不能直接地反映概率了。
#
# 预先给定$PR$值后，通过下面的算法不断迭代，直至达到平稳分布为止。
# 互联网中的众多网页可以看作一个有向图。下图是一个简单的例子：图中的节点表示网页，如果网页A有链接到网页B，则存在一条有向边A->B：
# 
# 这个例子中只有四个网页，如果当前在$A$网页，那么悠闲的上网者将会各以$1/3$的概率跳转到$B、C、D$,这里的3表示$A$有3条出链，如果一个网页有$k$条出链，那么跳转任意一个出链上的概率是$1/k$，同理$D$到$B$、$C$的概率各为$1/2$，而$B$到$C$的概率为0。一般用转移矩阵表示上网者的跳转概率，如果用$n$表示网页的数目，则转移矩阵$M$是一个$n*n$的方阵；如果网页$j$有$k$个出链，那么对每一个出链指向的网页$i$，有$M[i][j]=1/k$，而其他网页的$M[i][j]=0$；上面示例图对应的转移矩阵如下：
#
# \begin{equation}
# M={
# \left[ \begin{array}{cccc}
# 0 & 1/2 & 1 & 0\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 1/2 & 0 & 0
# \end{array}
# \right ]}
# \end{equation}
# 初始时，假设上网者在每一个网页的概率都是相等的，即$1/n$，于是初始的概率分布就是一个所有值都为$1/n$的$N$维列向量$V_0$，用$V_0$去右乘转移矩阵$M$，就得到了第一步之后上网者的概率分布向量$V_1$。下面是$V_1$的计算过程：
#
# \begin{equation}
# V_1 = MV_0 ={
# \left[ \begin{array}{cccc}
# 0 & 1/2 & 1 & 0\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 1/2 & 0 & 0
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]=
# \left[ \begin{array}{cccc}
# 9/24\\
# 5/24\\
# 5/24\\
# 5/24
# \end{array}
# \right ]}
# \end{equation}
# 注意矩阵M中$M[i][j]$不为0表示用一个链接从$j$指向$i$，$M$的第一行乘以$V_0$，表示累加所有网页到网页$A$的概率即得到$9/24$。得到了$V_1$后，再用$V_1$去右乘$M$得到$V_2$，一直下去，最终$V$会收敛，即$V_n=MV_{(n-1)}$，上面的图示例，不断的迭代，最终 $V=[3/9,2/9,2/9,2/9]^T$
#
# \begin{equation}
# {
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 9/24\\
# 5/24\\
# 5/24\\
# 5/24
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 15/48\\
# 11/48\\
# 11/48\\
# 11/48
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 11/32\\
# 7/32\\
# 7/32\\
# 7/32
# \end{array}
# \right ]
# ...
# \left[ \begin{array}{cccc}
# 3/9\\
# 2/9\\
# 2/9\\
# 2/9
# \end{array}
# \right ]}
# \end{equation}
# # 终止点问题
#
# 上述上网者的行为是一个马尔科夫过程的实例，要满足收敛，需要具备一个条件：
# **图是强连通的，即从任意网页可以到达其他的任意网页**
#
# 但是互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，如果按照上面的计算，上网者到达这样的网页后便走投无路，导致前面累计得到的转移概率被清零，这样下去，最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉，C变成了一个终止点，得到下面这个图：
#
# 
# 对应的转移矩阵为
#
# \begin{equation}
# M={
# \left[ \begin{array}{cccc}
# 0 & 1/2 & 0 & 0\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 1/2 & 0 & 0
# \end{array}
# \right ]}
# \end{equation}
#
# 连续迭代下去，最终所有元素都为$0$：
#
# \begin{equation}
# {
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 3/24\\
# 5/24\\
# 5/24\\
# 5/24
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 5/48\\
# 7/48\\
# 7/48\\
# 7/48
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 21/288\\
# 31/288\\
# 31/288\\
# 31/288
# \end{array}
# \right ]
# ...
# \left[ \begin{array}{cccc}
# 0\\
# 0\\
# 0\\
# 0
# \end{array}
# \right ]}
# \end{equation}
# # 陷阱问题
#
# 另外一个问题就是陷阱问题，即有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：
# 
#
# 上网者跑到C网页后，再也不能从C中出来，将最终导致概率分布值全部转移到C上来，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。
# 对应的转移矩阵为
#
# \begin{equation}
# M={
# \left[ \begin{array}{cccc}
# 0 & 1/2 & 0 & 0\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 0 & 1 & 1/2\\
# 1/3 & 1/2 & 0 & 0
# \end{array}
# \right ]}
# \end{equation}
#
# 连续迭代下去，最终所有元素都为$0$：
#
# \begin{equation}
# {
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 3/24\\
# 5/24\\
# 11/24\\
# 5/24
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 5/48\\
# 7/48\\
# 29/48\\
# 7/48
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 21/288\\
# 31/288\\
# 205/288\\
# 31/288
# \end{array}
# \right ]
# ...
# \left[ \begin{array}{cccc}
# 0\\
# 0\\
# 1\\
# 0
# \end{array}
# \right ]}
# \end{equation}
# # 解决方案
#
#
# 我们认为上网者，总是随机的选择网页，当走到一个终结网页或者一个陷阱网页时(比如两个示例中的$C$)，不会被困在原地，而是会在浏览器的地址随机输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会。为此我们对算法进行改进，每一步，上网者可能都不想看当前网页了，不看当前网页也就不会点击上面的链接，而是在地址栏输入另外一个地址，而在地址栏输入而跳转到各个网页的概率是$1/n$。假设上网者每一步查看当前网页的概率为$a$，那么他从浏览器地址栏跳转的概率为$(1-a)$，于是原来的迭代公式转化为：
#
# $$V = aMV+(1-a)e$$
# 根据上式来计算带有陷阱节点的网页图的最终的概率分布：
#
# \begin{equation}
# $$V = aMV+(1-a)e = 0.8 \times
# \left[ \begin{array}{cccc}
# 0 & 1/2 & 0 & 0\\
# 1/3 & 0 & 0 & 1/2\\
# 1/3 & 0 & 1 & 1/2\\
# 1/3 & 1/2 & 0 & 0
# \end{array}
# \right ]
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]+0.2 \times
# \left[ \begin{array}{cccc}
# 1/4\\
# 1/4\\
# 1/4\\
# 1/4
# \end{array}
# \right ]=
# \left[ \begin{array}{cccc}
# 9/60\\
# 13/60\\
# 25/60\\
# 13/60
# \end{array}
# \right ]
# \end{equation}
# In[4]:
import matplotlib.pyplot as plt
import networkx as nx
G=nx.barabasi_albert_graph(30,3)
layout = nx.spring_layout(G)
plt.figure(figsize=(15,8))
plt.subplot(121)
nx.draw(G, pos=nx.shell_layout(G), node_color='y')
pr=nx.pagerank(G,alpha=0.85
plt.subplot(122)
nx.draw(G, pos=nx.shell_layout(G), node_size=[x * 18000 for x in pr.values()],node_color='r',with_labels=True)
plt.show()
# In[1]:
# 算法实现
from numpy import *
import numpy
def transition(a): #构造转移矩阵
b = transpose(a)
c = zeros((a.shape),dtype = float)
for i in range(a.shape[0]):
for j in range(a.shape[1]):
c[i][j] = a[i][j]/(b[j].sum())
return c
def initial(c): #初始化每一个网页pagerank的
pr = zeros((c.shape[0],1),dtype = float) #构造一个存放pr值得矩阵
for i in range(c.shape[0]):
pr[i] = float(1)/c.shape[0]
return pr
def pageRank(p,m,v): #计算pageRank值
while((v == p*dot(m,v) + (1-p)*v).all()==False):
#判断pr矩阵是否收敛,(v == p*dot(m,v) + (1-p)*v).all()判断前后的pr矩阵是否相等，若相等则停止循环
#print(v)
v = p*dot(m,v) + (1-p)*v
#print((v == p*dot(m,v) + (1-p)*v).all())
return v
if __name__=="__main__":
network = numpy.loadtxt('./data.txt', delimiter=' ')
#print(network)
M = transition(network)
initvalue = initial(M)
p = 0.8
print(pageRank(p,M,initvalue))
# In[ ]:
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
G = nx.DiGraph()
edges = []
def transition(a): #构造转移矩阵
b = transpose(a)
c = zeros((a.shape),dtype = float)
for i in range(a.shape[0]):
for j in range(a.shape[1]):
c[i][j] = a[i][j]/(b[j].sum())
return c
def initial(c): #初始化每一个网页pagerank的
pr = zeros((c.shape[0],1),dtype = float) #构造一个存放pr值得矩阵
for i in range(c.shape[0]):
pr[i] = float(1)/c.shape[0]
return pr
def pageRank(p,m,v): #计算pageRank值
while((v == p*dot(m,v) + (1-p)*v).all()==False):
#判断pr矩阵是否收敛,(v == p*dot(m,v) + (1-p)*v).all()判断前后的pr矩阵是否相等，若相等则停止循环
v = p*dot(m,v) + (1-p)*v
#print((v == p*dot(m,v) + (1-p)*v).all())
return v
def read2networkx():# 读取文件中的网络数据
i=j=0
fin = open('data.txt', 'r')
for line in fin:
i = i + 1
line = line.strip().split()
j = 0
for x in line:
j = j + 1
if x == str(1):
edges.append((i, j))
G.add_edges_from(edges)
fin.close()
plt.figure(figsize=(20,8))
plt.subplot(121)
nx.draw(G, pos=nx.shell_layout(G), node_color='y',with_labels = True, node_size=3000, font_size = 30)
def drawGraph(value): #可视化
arg = np.argsort(-array(value))+1
color = ['maroon', 'slateblue', 'purple', 'magenta','salmon', 'c', 'gold', 'greenyellow', 'yellow', 'green']
colorDic = {}
for index in range(10):
colorDic[arg[index]] = color[index]
plt.subplot(122)
pos=nx.shell_layout(G)
nx.draw(G, pos, node_color=list(colorDic.values()),node_size = [x * 50000 for x in value],font_color = 'black')
labels={}
for index in range(10):
labels[arg[index]] = r'$r_{'+str(index+1)+'}$'
nx.draw_networkx_labels(G,pos,labels,font_size=40, font_color='black')
plt.show()
if __name__ == "__main__":
network = numpy.loadtxt('./data.txt', delimiter=' ')
M = transition(network)
initvalue = initial(M)
p = 0.8
value = pageRank(p,M,initvalue)
print(value)
value = array(array(value).flatten().tolist())
read2networkx()
drawGraph(value.tolist())
# # Thank You