二分网络研究 樊瑛 北京师范大学系统科学系 2010.08.09
复杂网络研究 概念和工具 拓扑结构性质:统计量及其分布 社团结构 演化模型 网络上的动力学 …
大纲 二分网络简介 二分网络中的社团结构 展望及思考
1、二分网络简介
二分网络 Bipartite graph
实际系统中的二分结构 Collaboration networks (agents-affairs) Many large real-world networks may be modeled naturally by a bipartite networks ,for example: 1 Actors-movies 2 Authors-papers 3 p2p networks 4 books-readers 5 soccer players 6 listeners-music genres 7 enterprises-banks 8 funds-stocks …… Collaboration networks (agents-affairs) Examples in biology systems? Metabolic network Human disease network Drugs –molecular targets
二分网络的投影(到单顶点网络)
投影的不足 信息的丢失 数目的膨胀 一些性质是由于投影所产生 Matthieu Latapy, Clemence Magnien, Nathalie Del Vecchio, Basic notions for the analysis of large two-mode networks, social networks,30(2008)31-48.
加权投影 How to project a bipartite networks? Zhou Tao et.al PRE 76.046115(2007) How to project a bipartite networks?
网络的统计量 Basic notions for the analysis of large two-mode networks, social networks,30(2008)31-48
度及度分布 Basic notions for the analysis of large two-mode networks, social networks,30(2008)31-48
二分集聚系数 Cumulative distribution Basic notions for the analysis of large two-mode networks, social networks,30(2008)31-48
集聚系数C4 Pedro G. Lind, Marta C. González, Hans J. Herrmann Cycles and clustering in bipartite networks PHYSICAL REVIEW E 72, 056127 2005
我们定义的C4 quadrangle
边集聚系数(LC4)
边集聚系数(LC3)
边集聚系数(LC3)
最短路径 介数
网络的演化 依附网 非依附网
网络上的动力学 靴襻渗流 带有物理意义或实际意义的动力学的设计
2、二分网络中的社团结构
描述性定义
二模式矩阵 Correspondence analysis Network analysis of 2-mode data, social networks,19(1997)243-269
对应分析
子群
Ka,b双派系方法 带有重叠的社团结构(overlapping) Lehmann S, Schwartz M, Hansen L K. Biclique communities[J]. Physical Review E, 2008, 78: 016108.
基于边集聚系数的分裂算法 过程 1 计算每条边的集聚系数 2 断掉边集聚系数最小的边 3 返回1,直到断开所有边。
人工网络(检验网络) 0——15 16——31 32——47 48——63 0——15 16——31 32——47 48——63
结果
实际网络 经济物理学科学家合作网 北师大图书借阅网
二分网络中的Q函数 Module identification in bipartite and directed networks, PHYSICAL REVIEW E 76, 036102 2007
其他算法 基于比较性定义的二分网络聚类方法 基于资源分布矩阵的二分网络聚类方法
一个例子 {A,B, C}, {D, E, F}
3 展望与思考 二分网络的研究 数据的获取 基于二分网络原始信息对网络性质的分析 在实际系统中的应用 系统科学与复杂网络
谢谢大家!