复杂网络综述ppt课件.ppt

1、多层网络模型及其应用孙佩源2017年4月19日11. 背景 现实网络（社交网络、引用网络、脑网络等）并非完全随机 节点度服从power law（Scale Free） 节点间平均路径长度很小（Small World） 现实网络动态增长 节点加入、撤离；边的添加、删除及重连接等 仍保持Scale Free和Small World特性 现实网络通常呈现多层特性 节点间存在多种连接关系 交通网络：公路，地铁，高铁等 层间关系影响网络的增长22. Erdos-Renyi Model 假设节点间边的生成互相独立 整个网络的似然度为： 节点度分布为：1( )(1)ijijaaijlikelihood Gp

2、p()( )!knpnpep kk泊松分布泊松分布静态网路静态网路单层网络单层网络3 Barbieri, Nicola, Francesco Bonchi, and Giuseppe Manco. Who to follow and why: link prediction with explanations. KDD2014. 假设网络由ER生成过程生成（Dirichlet Distribution, Beta Distribution） 通过节点上附着的标签信息推测边的存在及生成原因 S. W. Linderman and R. P. Adams. Discovering latent n

3、etwork structure in point process data. ICML2014. 假设网络由ER生成过程生成 通过在该网络上的扩散数据推测边的存在 Peiyuan Sun. Inferring Multiplex Diffusion Network via Multivariate Marked Hawkes Process. 扩展至多层网络（仍基于ER生成过程）2. Erdos-Renyi Model泊松分布泊松分布静态网路静态网路单层网络单层网络4 优点 简单高效 易与机器学习中概率图模型结合 缺点 与现实网络有出入 节点度为泊松分布而非幂律分布 不存在小世界现象 集群现

4、象也很少见 效果一般 扩展的Watts-Strogatz网络满足Small World和Clustering，但仍为静态单层网络2. Erdos-Renyi Model泊松分布泊松分布静态网路静态网路单层网络单层网络53. BA Model 每个时刻加入一个节点并引入m条边 网络中已存在节点i吸引其中一条边的概率为： 该模型生成网络满足节点度的幂律分布 由生成过程可知为动态网络模型幂律幂律分布分布动态动态网路网路单层网络单层网络( )iijjkkkPreferential Attachment63. BA Model 单个节点的度演化：幂律幂律分布分布动态动态网路网路单层网络单层网络( )=2

5、2iiijjiikmktkmkkmmtkt0.5( )( )iitk tmt73. BA Model 整个网络度分布：幂律幂律分布分布动态动态网路网路单层网络单层网络2222220( ( )()1()1()iiim tp k tkp tkm tp tkm tktm 2303( ( )( )21ip k tkp kkm tmt kAk8 优点 简单 节点度满足幂律分布，且为动态网络 缺点 仍然与现实网络有出入 集群现象很弱 现实网络中节点度分布指数多有出入 只能作为一个解释型模型 用于生成随机网络 如LFRbenchmark即基于此模型的改进生成随机图Lancichinetti A, Fortu

6、nato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.J. Physical Review E,2009.（引用量477）3. BA Model幂律幂律分布分布动态动态网路网路单层网络单层网络94. PA Model with initial attractiveness 每个网络节点s拥有一个初始的吸引参数： 每个时刻加入一个节点并引入m条边 网络中已存在节点s吸引其中一条边的概率为： 该模型生成网络满

7、足节点度的幂律分布 由生成过程可知为动态网络模型幂律幂律分布分布动态动态网路网路单层网络单层网络( , )()sqAs tmA tA104. PA Model with initial attractiveness 网络模型中非常有用的套路： Difference Equation & Generating Function Method 该模型的Master Equation为：幂律幂律分布分布动态动态网路网路单层网络单层网络114. PA Model with initial attractiveness 求解该Master Equation： 在t很大时，将差分转化为微分 在t很大时，假

8、设网络分布极限存在幂律幂律分布分布动态动态网路网路单层网络单层网络124. PA Model with initial attractiveness 求解该Difference Equation： 假设生成函数： 以及一些基本推论：幂律幂律分布分布动态动态网路网路单层网络单层网络134. PA Model with initial attractiveness 通过Generating Function转换为如下的Differential Equation: 这里可以套用教科书中的经典结论求解之 对比求解结果中Z的各次项系数可得：幂律幂律分布分布动态动态网路网路单层网络单层网络144. PA

9、Model with initial attractiveness 类比该套路可得单节点的度随时间变化公式： 同时可得单节点度指数与整个网络度分布指数关系：幂律幂律分布分布动态动态网路网路单层网络单层网络154. PA Model with initial attractiveness 优点： 克服了BA Model中度分布指数为3的局限性 得出了单节点度指数与整个网络度分布指数的关系 该模型假设较少，成为很多后续模型的基础Dorogovtsev S N, Mendes J F, Samukhin A N. Structure of growing networks with preferen

10、tial linking.J. Physical Review Letters, 2000（引用量1385） 缺点： 在网络度分布为2时失效 集群现象较弱 仅考虑单层幂律幂律分布分布动态动态网路网路单层网络单层网络165. Popularity versus Similarity Model 生成过程：幂律幂律分布分布动态动态网路网路单层网络单层网络175. Popularity versus Similarity Model 证明思路： 求解图中红色区域的半径 落入该区域中节点的期望数为m hyperbolic distance小于半径 得到网络中已有节点吸引一条新边 的概率等价于Model

11、4 则单节点度演化及网络度分布等价 于Model4中结论幂律幂律分布分布动态动态网路网路单层网络单层网络185. Popularity versus Similarity Model 模型变种：1. 将与最近的m个节点连接扩展为 随机选择节点并以特定概率连接2. 尝试与每个节点以特定概率连接3. 除了新节点加入的m条边，已有 节点间也以一定概率生成边幂律幂律分布分布动态动态网路网路单层网络单层网络19()/1()ststxR Tp xe5. Popularity versus Similarity Model 扩展的意义：1. 逐步加入缺失的现实因素2. 生成的网络尽量与现实网络拟合幂律幂律分

12、布分布动态动态网路网路单层网络单层网络20网络度分布平均集群系数平均邻居节点度距离分布平均中间性节点诞生与度分布5. Popularity versus Similarity Model 坐标求解：1. 根据全局极大似然度得出流行度坐标： 节点度越大其出现时间越早2. 根据每个节点的连接关系计算相似度坐标： 应用：1. 根据现实网络拓扑计算节点的坐标2. 可用于社区检测和链接预测幂律幂律分布分布动态动态网路网路单层网络单层网络21/305. Popularity versus Similarity Model 社区检测幂律幂律分布分布动态动态网路网路单层网络单层网络相似度坐标接近的节点地理上属

13、于同一国家22/305. Popularity versus Similarity Model 链接预测幂律幂律分布分布动态动态网路网路单层网络单层网络在难预测链接上性能优于目前已有方法存在于低度节点间且没有公共邻居23/30 优点： 克服了Model4中度分布指数为2时失效的情形 可以通过模型参数调节网络的集群现象强度 融入节点的相似度信息Papadopoulos F, Kitsak M, Serrano M , et al. Popularity versus similarity in growing networks.J. Nature, 2012.（引用量180） 缺点： 仅考虑单层

14、245. Popularity versus Similarity Model幂律幂律分布分布动态动态网路网路单层网络单层网络6. Growing Multiplex Network Model 生成过程：1. 每个时刻网络加入一个新增节点i2. 该节点在每层均有一个stub节点并引入m条边3. 层中j节点吸引其中一条边的概率为：幂律幂律分布分布动态动态网路网路两两层层网络网络11121112()( )=()jijlljjjjlF kF kc kc kc kc k F为同一节点在两层中度的线性组合函数25/306. Growing Multiplex Network Model Master

15、Equation:1. 设 为t时刻第1层节点度为k，第2层节点度为q的节点的数目2. 函数当k=q时为1，其他为0 幂律幂律分布分布动态动态网路网路两两层层网络网络,( )k qNt,k q新加入节点度为（k,q）时t时刻度为（k,q）且发生变化通过吸引一条新加入的边度变为（k,q）初始条件26/306. Growing Multiplex Network Model 结论:1. 当两层节点同步到达时，即使关联系数为0，仍然存在耦合关系2. 当第2层节点到达时间为幂律延迟时，延迟指数 显著影响层间关联性 越小，层间关联性越低 幂律幂律分布分布动态动态网路网路两两层层网络网络27/306. Growing Multiplex Network Model 优点: 首次提出多层网络增长模型 刻画了节点延迟对层间关联强度的影响 缺点： 基于PA模型，所以也遗传了PA相应的缺点 只能用于解释，基本无法应用幂律幂律分布分布动态动态网路网路两两层层网络网络28/30总结29/30模型模型度分布度分布集群系数集群系数动态动态/静态静态单层单层/多层多层ER泊松分布弱静态单层BA幂律分布弱动态单层PAE幂律分布弱动态单层PSO幂律分布可调节动态单层GMM幂律分布弱动态两层谢谢大家！30/30