复杂网络综述课件

多层网络模型及其应用孙佩源2017年4月19日1多层网络模型及其应用孙佩源11.背景现实网络（社交网络、引用网络、脑网络等）并非完全随机节点度服从power law（Scale Free）节点间平均路径长度很小（Small World）现实网络动态增长节点加入、撤离；边的添加、删除及重连接等仍保持Scale Free和Small World特性现实网络通常呈现多层特性节点间存在多种连接关系交通网络：公路，地铁，高铁等层间关系影响网络的增长21.背景现实网络（社交网络、引用网络、脑网络等）并非完全随2.Erdos-Renyi Model假设节点间边的生成互相独立整个网络的似然度为：节点度分布为：泊松分布泊松分布静静态网路网路单层网网络32.Erdos-Renyi Model假设节点间边的生成互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 network structure in point process data.ICML2014.假设网络由ER生成过程生成通过在该网络上的扩散数据推测边的存在Peiyuan Sun.Inferring Multiplex Diffusion Network via Multivariate Marked Hawkes Process.扩展至多层网络（仍基于ER生成过程）2.Erdos-Renyi Model泊松分布泊松分布静静态网路网路单层网网络4Barbieri,Nicola,Francesco Bo优点简单高效易与机器学习中概率图模型结合缺点与现实网络有出入节点度为泊松分布而非幂律分布不存在小世界现象集群现象也很少见效果一般扩展的Watts-Strogatz网络满足Small World和Clustering，但仍为静态单层网络2.Erdos-Renyi Model泊松分布泊松分布静静态网路网路单层网网络5优点2.Erdos-Renyi Model泊松分布静态网路3.BA Model每个时刻加入一个节点并引入m条边网络中已存在节点i吸引其中一条边的概率为：该模型生成网络满足节点度的幂律分布由生成过程可知为动态网络模型幂律律分布分布动态网路网路单层网网络Preferential Attachment63.BA Model每个时刻加入一个节点并引入m条边幂律分3.BA Model单个节点的度演化：幂律律分布分布动态网路网路单层网网络73.BA Model单个节点的度演化：幂律分布动态网路单层3.BA Model整个网络度分布：幂律律分布分布动态网路网路单层网网络83.BA Model整个网络度分布：幂律分布动态网路单层网优点简单节点度满足幂律分布，且为动态网络缺点仍然与现实网络有出入集群现象很弱现实网络中节点度分布指数多有出入只能作为一个解释型模型用于生成随机网络如LFRbenchmark即基于此模型的改进生成随机图Lancichinetti A,Fortunato S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities.J.Physical Review E,2009.（引用量477）3.BA Model幂律律分布分布动态网路网路单层网网络9优点3.BA Model幂律分布动态网路单层网络94.PA Model with initial attractiveness每个网络节点s拥有一个初始的吸引参数：每个时刻加入一个节点并引入m条边网络中已存在节点s吸引其中一条边的概率为：该模型生成网络满足节点度的幂律分布由生成过程可知为动态网络模型幂律律分布分布动态网路网路单层网网络104.PA Model with initial attra4.PA Model with initial attractiveness网络模型中非常有用的套路：Difference Equation&Generating Function Method该模型的Master Equation为：幂律律分布分布动态网路网路单层网网络114.PA Model with initial attra4.PA Model with initial attractiveness求解该Master Equation：在t很大时，将差分转化为微分在t很大时，假设网络分布极限存在幂律律分布分布动态网路网路单层网网络124.PA Model with initial attra4.PA Model with initial attractiveness求解该Difference Equation：假设生成函数：以及一些基本推论：幂律律分布分布动态网路网路单层网网络134.PA Model with initial attra4.PA Model with initial attractiveness通过Generating Function转换为如下的Differential Equation:这里可以套用教科书中的经典结论求解之对比求解结果中Z的各次项系数可得：幂律律分布分布动态网路网路单层网网络144.PA Model with initial attra4.PA Model with initial attractiveness类比该套路可得单节点的度随时间变化公式：同时可得单节点度指数与整个网络度分布指数关系：幂律律分布分布动态网路网路单层网网络154.PA Model with initial attra4.PA Model with initial attractiveness优点：克服了BA Model中度分布指数为3的局限性得出了单节点度指数与整个网络度分布指数的关系该模型假设较少，成为很多后续模型的基础Dorogovtsev S N,Mendes J F,Samukhin A N.Structure of growing networks with preferential linking.J.Physical Review Letters,2000（引用量1385）缺点：在网络度分布为2时失效集群现象较弱仅考虑单层幂律律分布分布动态网路网路单层网网络164.PA Model with initial attra5.Popularity versus Similarity Model生成过程：幂律律分布分布动态网路网路单层网网络175.Popularity versus Similarit5.Popularity versus Similarity Model证明思路：求解图中红色区域的半径落入该区域中节点的期望数为mhyperbolic distance小于半径得到网络中已有节点吸引一条新边 的概率等价于Model4则单节点度演化及网络度分布等价 于Model4中结论幂律律分布分布动态网路网路单层网网络185.Popularity versus Similarit5.Popularity versus Similarity Model模型变种：1.将与最近的m个节点连接扩展为 随机选择节点并以特定概率连接2.尝试与每个节点以特定概率连接3.除了新节点加入的m条边，已有 节点间也以一定概率生成边幂律律分布分布动态网路网路单层网网络195.Popularity versus Similarit5.Popularity versus Similarity Model扩展的意义：1.逐步加入缺失的现实因素2.生成的网络尽量与现实网络拟合幂律律分布分布动态网路网路单层网网络20网络度分布平均集群系数平均邻居节点度距离分布平均中间性节点诞生与度分布5.Popularity versus Similarit5.Popularity versus Similarity Model坐标求解：1.根据全局极大似然度得出流行度坐标：节点度越大其出现时间越早2.根据每个节点的连接关系计算相似度坐标：应用：1.根据现实网络拓扑计算节点的坐标2.可用于社区检测和链接预测幂律律分布分布动态网路网路单层网网络21/305.Popularity versus Similarit5.Popularity versus Similarity Model社区检测幂律律分布分布动态网路网路单层网网络相似度坐标接近的节点地理上属于同一国家22/305.Popularity versus Similarit5.Popularity versus Similarity Model链接预测幂律律分布分布动态网路网路单层网网络在难预测链接上性能优于目前已有方法存在于低度节点间且没有公共邻居23/305.Popularity versus Similarit优点：克服了Model4中度分布指数为2时失效的情形可以通过模型参数调节网络的集群现象强度融入节点的相似度信息Papadopoulos F,Kitsak M,Serrano M,et al.Popularity versus similarity in growing networks.J.Nature,2012.（引用量180）缺点：仅考虑单层245.Popularity versus Similarity Model幂律律分布分布动态网路网路单层网网络优点：245.Popularity versus Simi6.Growing Multiplex Network Model生成过程：1.每个时刻网络加入一个新增节点i2.该节点在每层均有一个stub节点并引入m条边3.层中j节点吸引其中一条边的概率为：幂律律分布分布动态网路网路两两层网网络F为同一节点在两层中度的线性组合函数25/306.Growing Multiplex Network M6.Growing Multiplex Network ModelMaster Equation:1.设 为t时刻第1层节点度为k，第2层节点度为q的节点的数目2.函数当k=q时为1，其他为0 幂律律分布分布动态网路网路两两层网网络新加入节点度为（k,q）时t时刻度为（k,q）且发生变化通过吸引一条新加入的边度变为（k,q）初始条件26/306.Growing Multiplex Network M6.Growing Multiplex Network Model结论:1.当两层节点同步到达时，即使关联系数为0，仍然存在耦合关系2.当第2层节点到达时间为幂律延迟时，延迟指数 显著影响层间关联性 越小，层间关联性越低 幂律律分布分布动态网路网路两两层网网络27/306.Growing Multiplex Network M6.Growing Multiplex Network Model优点:首次提出多层网络增长模型刻画了节点延迟对层间关联强度的影响缺点：基于PA模型，所以也遗传了PA相应的缺点只能用于解释，基本无法应用幂律律分布分布动态网路网路两两层网网络28/306.Growing Multiplex Network M总结29/30模型模型度分布度分布集群系数集群系数动态/静静态单层/多多层ER泊松分布弱静态单层BA幂律分布弱动态单层PAE幂律分布弱动态单层PSO幂律分布可调节动态单层GMM幂律分布弱动态两层总结29/30模型度分布集群系数动态/静态单层/多层ER泊松谢谢大家！30/30谢谢大家！30/30