社团结构分析-全国复杂网络学术会议.pptVIP

* * * * * * * * * * * * * * * * * 生物信息学与最优化方法 * Finding 2 Finding 3 解析解表明，对这两个经典的算例，Q和D都有Resolution limit和Misidentification的现象产生，所以Q 和D均只是近似的定量评估函数。 网络社团划分的问题可以用一个优化问题来精确 描述，我们证明了这一模型是NP-hard的。 我们相信用优化理论可以彻底解决网络社团划分 的问题。网络科学是运筹学的下一个热点。 * 直接得到团环网络的社团结构数值解 * 直接得到ad hoc网络的社团结构数值解 * * * 为了彻底解决这些问题 提出一个新的 OR 模型和相应的算法，这一算法不会产生resolution limit 和 mis-identification 现象 关键思路：模块分划质量函数的定义要包含社团定义。 Xiang-Sun Zhang, Zhenping Li, Rui-Sheng Wang, Yong Wang. A combinatorial model and algorithm for globally searching community structure in complex networks Journal of Combinatorial Optimization (JCO), 2010. DOI: 10.1007/s10878-010-9356-0 A new OR model Problem definition: Given a network, the community identification problem is to partition the network into as many non-overlapping sub-networks as possible such that each sub-network satisfies a given community definition. 给定一个网络和一个社团的定义，社团结构识别的问题就是将整个网络分成尽可能多的满足社团定义的子网络。 * 以上文字定义可以用一个整数线性规划来描述 我们证明了这个模型是 NP-hard . * A qualified min-cut (QMC) algorithm A heuristic principle is given to find a feasible partition with the largest number of communities. It is realized by a min-cut operation: A min-cut operation is called qualified if the two resulting sub-networks satisfy the module definition. The community identification problem can be solved based on a series of qualified min-cut operations. * Experiment results (artificial networks) Rings of cliques Uneven ad-hoc network * Experiment results (real networks) Football team network Jazz musician network * 学术性的，实用性的问题远远没有解决 Yong-Yeol Ahn, James P. Bagrow Sune Lehmann，Nature, 2010 Link communities reveal multiscale complexity in networks * 致谢 This work is cooperated with Dr. 李珍萍，Dr. 王瑞省，Dr. 王勇，Dr. 张世华， Dr. 王吉光，Dr. 张俊华 This work is supported by 国家自然科学重点基 973项目2066CB503905 国家自然科学基金项 * Thanks Welcome to visit us at * * * * * * * * * * 含义