|||
小世界现象和无标度特性的发现引领了探索复杂网络演化机制的热潮。富者越富、好者变富是从宏观的层面上进行定义,群组和社区是中观网络结构的特征,同质性、聚类效应和平衡理论则是网络微观层面上的研究。然而,以上的研究都是针对无向网络的,尽管有向网络广泛存在,对于有向网络中潜在局部驱动机制的认识要远远少于无向网络。
本文提出的势能理论正是对有向网络微观结构一种新的刻画。势能理论假设,给定一个有向图,节点的势能沿着边的方向降低一单位的能量;若一个子图中所有节点的势能都可确定,则称此图是可定义势的。可定义势的结构有很多,但将势能理论同聚类性和同质性联系起来,便可推断出由4个节点和4条有向边所组成的Bi-fan结构应是有向网络中最显著的(参考下图)。文章基于链路预测模型在15个真实网络中验证了这一推断:Bi-fan对应的预测器的预测效果最准确也最稳定。
文章的理论意义在于对有向网络的微观构成有了更深刻的认识。可定义势的性质暗示了一个局部的层级结构,而且一个节点的势能体现了它在层级结构中的地位。层级结构对于无向网络和有向网络来说,都是非常著名的宏观结构特征;而文中工作表明,在有向网络中节点会倾向于在局部范围以分层的方式进行自组织。我们猜测这种微观的层级结构对于宏观的层级结构是很大相关性的。此研究还有很大的应用价值。链路预测实验表明,基于Bi-fan的预测器的预测精度要比基于共同邻居的预测方法优秀很多。此方法可直接应用于缺失连边的挖掘和好友关系的推荐——譬如新浪微博的关注对象推荐。
文章信息:Q.-M. Zhang, L. Lu, W.-Q. Wang, Y.-X. Zhu, T. Zhou, Potential Theory for Directed Networks, PLoS ONE 8 (2013) e55437.
文章链接:
http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0055437
全文下载:
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-24 10:41
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社