社团结构显著性

1、社团结构的显著性樊瑛北京师范大学管理学院系统科学系北京师范大学复杂性研究中心2010年10月17日合作者n胡延庆，博士生n王 洋，硕士生n丁义明，中科院武汉数学物理研究所n狄增如，北京师范大学系统科学系大纲n复杂网络中的社团结构n社团结构的显著性n显著性的衡量指标n小结与展望社团结构的描述性定义 community structure （集团结构）（集团结构） is the groups of network vertices. within these groups there have dense internal links, but between groups there are f

2、ewer edges. m. e. j. newman, eur. phys. j. b 38, 321-330 (2004) 评价函数-modularity2iiiiqea2tre- eiijjae1 ( ,)22vwijvwvwk kqac cmm212nvvvldqll基于q函数优化的聚类算法 q函数的缺点1 随机网络中也能得到较高的q值（0.8左右）。2 对于大规模网络中较小社团的探测。3 性质复杂（landscape）。 社团结构研究中的重要问题n最优分类数的确定（最优的划分）n最优的划分是否是显著的？n社团结构的鲁棒性n社团结构的显著性已有关于显著性的工作ngfeller等 加权网

3、络上的随机扰动和鲁棒性分析方法。nkarrer等 社团结构的鲁棒性问题：保持度序列不变下的对连边的随机扰动，之后利用信息熵测度集团结构之间的相似性，设计了指标v来衡量鲁棒性。n统计物理学的角度刻画社团结构的显著性，nmassen&doye 将负q对应为正则系综的能量，试图利用温度趋于绝对零度时的基态性质刻画社团结构的显著性；nbianconi等 利用熵的概念，讨论一定的社团结构与相同度序列随机网络的相关关系，用以考察社团结构是否仅仅是其他结构性质的衍生产物；nlancichinetti等 试图通过与随机网络的比较，确定某个社团的显著性。 n以上工作的局限：n通常以给定的社团结构为评价基

4、础，需要首先给出社团结构；n没有形成与网络规模等因素无关的普适的评价指标。研究工作重点n网络的社团结构性质与具体的划分技术无关，应该完全包含在原始的链接矩阵中，我们有必要直接基于原始的链接矩阵来刻画网络社团结构的显著性。n连接矩阵n拉普拉斯矩阵n二分类问题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空间鲁棒性的指标，也可以作为衡量社团结构显著性的指标。衡量指标的进一步修正nr指标的实际使用n不同网络之间的比较n最显著的、最模糊的情形n进行归一 特征值的分布受到网络平均度与度分布的影响特征值的取值与网络和社团的规模没有关系显著性衡量指标h显著性高，h值越小，最小值接近1。近似取值区间【0，1】在人工网上的检验结果在实际系统中的应用最佳分类数c的确定实际系统中的应用小结与展望1 指标r、h可以衡量网络社团结构的显著性，直接基于连接矩阵。2 指标r可以推广应用到