社团结构的显著性.ppt

社团结构的显著性,樊瑛 北京师范大学管理学院系统科学系 北京师范大学复杂性研究中心 2010年10月17日,合作者,胡延庆，博士生 王 洋，硕士生 丁义明，中科院武汉数学物理研究所 狄增如，北京师范大学系统科学系,大纲,复杂网络中的社团结构 社团结构的显著性 显著性的衡量指标 小结与展望,社团结构的描述性定义,Community structure （集团结构） is the groups of network vertices. Within these groups there have dense internal links, but between groups there are fewer edges.,M. E. J. Newman, Eur. Phys. J. B 38, 321-330 (2004),评价函数-Modularity,基于Q函数优化的聚类算法,Q函数的缺点,1 随机网络中也能得到较高的Q值（0.8左右）。 2 对于大规模网络中较小社团的探测。 3 性质复杂（landscape）。,社团结构研究中的重要问题,最优分类数的确定（最优的划分） 最优的划分是否是显著的？ 社团结构的鲁棒性 社团结构的显著性,已有关于显著性的工作,Gfeller等 加权网络上的随机扰动和鲁棒性分析方法。 Karrer等 社团结构的鲁棒性问题：保持度序列不变下的对连边的随机扰动，之后利用信息熵测度集团结构之间的相似性，设计了指标V来衡量鲁棒性。 统计物理学的角度刻画社团结构的显著性， Massen&Doye 将负Q对应为正则系综的能量，试图利用温度趋于绝对零度时的基态性质刻画社团结构的显著性； Bianconi等 利用熵的概念，讨论一定的社团结构与相同度序列随机网络的相关关系，用以考察社团结构是否仅仅是其他结构性质的衍生产物； Lancichinetti等 试图通过与随机网络的比较，确定某个社团的显著性。 以上工作的局限： 通常以给定的社团结构为评价基础，需要首先给出社团结构； 没有形成与网络规模等因素无关的普适的评价指标。,研究工作重点,网络的社团结构性质与具体的划分技术无关，应该完全包含在原始的链接矩阵中，我们有必要直接基于原始的链接矩阵来刻画网络社团结构的显著性。,连接矩阵 拉普拉斯矩阵 二分类问题,Newman, M. E. J. (2006) Finding community structure in networks using the eigenvectors of matrices. Phys. Rev.E. 74: 036104.,推广到多分类情形,n 个节点， c个社团,特征向量,特征值,研究SSU空间的鲁棒性 链接矩阵的拉普拉斯矩阵特征值和特征向量的影响,矩阵分析的稳定性理论,R可以作为衡量SSU空间鲁棒性的指标，也可以作为衡量社团结构显著性的指标。,衡量指标的进一步修正,R指标的实际使用 不同网络之间的比较 最显著的、最模糊的情形 进行归一,特征值的分布,受到网络平均度与度分布的影响,特征值的取值,与网络和社团的规模没有关系,显著性衡量指标H,显著性高，h值越小，最小值接近1。,近似取值区间【0，1】,在人工网上的检验结果,在实际系统中的应用,最佳分类数C的确定,实际系统中的应用,小结与展望,1 指标R、H可以衡量网络社团结构的显著性，直接基于连接矩阵。 2 指标R可以推广应用到最佳分类数的