欢迎来到天天文库
浏览记录
ID:52419599
大小:783.93 KB
页数:30页
时间:2020-04-06
《复杂网络综述.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、多层网络模型及其应用孙佩源2017年4月19日11.背景现实网络(社交网络、引用网络、脑网络等)并非完全随机节点度服从powerlaw(ScaleFree)节点间平均路径长度很小(SmallWorld)现实网络动态增长节点加入、撤离;边的添加、删除及重连接等仍保持ScaleFree和SmallWorld特性现实网络通常呈现多层特性节点间存在多种连接关系交通网络:公路,地铁,高铁等层间关系影响网络的增长22.Erdos-RenyiModel假设节点间边的生成互相独立整个网络的似然度为:节点度分布为:泊松分布静态网路单层网络3Barbieri,N
2、icola,FrancescoBonchi,andGiuseppeManco."Whotofollowandwhy:linkpredictionwithexplanations."KDD2014.假设网络由ER生成过程生成(DirichletDistribution,BetaDistribution)通过节点上附着的标签信息推测边的存在及生成原因S.W.LindermanandR.P.Adams.Discoveringlatentnetworkstructureinpointprocessdata.ICML2014.假设网络由ER生成过程生成
3、通过在该网络上的扩散数据推测边的存在PeiyuanSun.InferringMultiplexDiffusionNetworkviaMultivariateMarkedHawkesProcess.扩展至多层网络(仍基于ER生成过程)2.Erdos-RenyiModel泊松分布静态网路单层网络4优点简单高效易与机器学习中概率图模型结合缺点与现实网络有出入节点度为泊松分布而非幂律分布不存在小世界现象集群现象也很少见效果一般扩展的Watts-Strogatz网络满足SmallWorld和Clustering,但仍为静态单层网络2.Erdos-Ren
4、yiModel泊松分布静态网路单层网络53.BAModel每个时刻加入一个节点并引入m条边网络中已存在节点i吸引其中一条边的概率为:该模型生成网络满足节点度的幂律分布由生成过程可知为动态网络模型幂律分布动态网路单层网络PreferentialAttachment63.BAModel单个节点的度演化:幂律分布动态网路单层网络73.BAModel整个网络度分布:幂律分布动态网路单层网络8优点简单节点度满足幂律分布,且为动态网络缺点仍然与现实网络有出入集群现象很弱现实网络中节点度分布指数多有出入只能作为一个解释型模型用于生成随机网络如LFRbenc
5、hmark即基于此模型的改进生成随机图LancichinettiA,FortunatoS.Benchmarksfortestingcommunitydetectionalgorithmsondirectedandweightedgraphswithoverlappingcommunities.[J].PhysicalReviewE,2009.(引用量477)3.BAModel幂律分布动态网路单层网络94.PAModelwithinitialattractiveness每个网络节点s拥有一个初始的吸引参数:每个时刻加入一个节点并引入m条边网络中
6、已存在节点s吸引其中一条边的概率为:该模型生成网络满足节点度的幂律分布由生成过程可知为动态网络模型幂律分布动态网路单层网络104.PAModelwithinitialattractiveness网络模型中非常有用的套路:DifferenceEquation&GeneratingFunctionMethod该模型的MasterEquation为:幂律分布动态网路单层网络114.PAModelwithinitialattractiveness求解该MasterEquation:在t很大时,将差分转化为微分在t很大时,假设网络分布极限存在幂律分布动
7、态网路单层网络124.PAModelwithinitialattractiveness求解该DifferenceEquation:假设生成函数:以及一些基本推论:幂律分布动态网路单层网络134.PAModelwithinitialattractiveness通过GeneratingFunction转换为如下的DifferentialEquation:这里可以套用教科书中的经典结论求解之对比求解结果中Z的各次项系数可得:幂律分布动态网路单层网络144.PAModelwithinitialattractiveness类比该套路可得单节点的度随时间
8、变化公式:同时可得单节点度指数与整个网络度分布指数关系:幂律分布动态网路单层网络154.PAModelwithinitialattractiveness优点:克服了
此文档下载收益归作者所有