复杂网络健壮社团挖掘算法.docVIP

 复杂网络健壮社团挖掘算法# 靳二辉，马小科，高琳** （西安电子科技大学计算机学院，西安 710071） 5 摘要：提出了一种基于贝叶斯网络的健壮社团挖掘算法，通过对每个普通社团分别构建贝叶 斯网络，并根据条件概率表和证据信息进行推理，得到贝叶斯网络中每个结点隶属于健壮社 团的后验概率以提取健壮社团。试验结果表明该方法对健壮社团发现的有效性。 关键词：复杂网络；社团发现；健壮社团；贝叶斯网络 中图分类号：TP391.4 10 A novel algorithm for the robust community in complex networks Jin Erhui, Ma Xiaoke, Gao Lin (School of Computer Science and Technology, Xidian University, Xi’an 710071) 15 20 25 30 35 Abstract: In this paper, a Bayesian network based algorithm for robust community in complex network is developed. Through constructing Bayesian network for every common community, according to conditional probabilities table and prior probabilities for reasoning, the posterior probabilities of every node being in a robust community is obtained to extract robust communities. Finally, we experimentally verify the effectiveness of two algorithms in networks. Keywords: Complex network; Community discovering; Robust community; Bayesian network 0 引言 随着对网络性质的物理意义和数学特性的深入研究，网络的概念被越来越广泛地应用在 各个领域，例如万维网、流行病学、科学引文和合作、代谢系统以及生态系统等。人们发现 许多真实网络中都存在着一个重要的特性——社团（即模块）结构，即整个网络是由若干个 社团构成的，这些社团具有内紧外松的结构特征。例如，WWW 可以看作是由大量网站社 团组成，根据网站所讨论的话题的性质将网络划分为不同的社团。类似地，在生物网络或者 电路网络中，也可根据各个节点不同的功能特性划分为不同的社团。各个社团内部节点间连 接相对紧密，各个社团之间的连接却相对稀疏。 然而，一般情况下找到网络中社团结构的精确解是一个 NP 难题。当网络的规模较大时， 解决上述问题有许多试探性算法，其中比较著名的两个算法包括： （1）基于 Laplacian 图形特征值的谱平分法[1]：该算法是基于各个顶点之间连接的相 似度（也称相似性），把网络划分为各个社团。根据向网络中添加连边或者从网络中移除边， 该类算法又可分为凝聚方法和分裂方法； （2）Kernighan-Lin 算法[2]：它采用了一种贪婪算法，根据使社团内部及社团间的边最 优化的原则对原始的网络进行分类。 本文将以如何检测出复杂网络中的健壮社团为主要内容展开详细论述，提出两种健壮社 团发现算法，分别为：基于贝叶斯网络的健壮社团发现算法和基于矩阵扰动理论的健壮社团 发现算法。通过实验仿真证明了两种算法用于解决该问题的有效性。 基金项目：高等学校博士学科点专项科研基金（200807010013） 作者简介：靳二辉，（1984-），女，主要研究方向：复杂网络。 通信联系人：高琳，（1964-），女，教授，博导。研究方向：生物信息学，数据挖掘。 E-mail: lgao@ -1-  40 45 50 55 60 65  1 基于贝叶斯网络的健壮社团发现算法 在具体应用中，系统往往只关注于局部覆盖而非全局划分，如蛋白质相互作用网络，社 团对应于具备某种特定功能的蛋白质复合体，而研究者更关注于复合体中的核心部分，称之 为健壮社团。如何挖掘出有特定意义的健壮社团具有重要的现实意义与应用价值。 本节提出了一种基于贝叶斯网络推理的健壮社团发掘算法。利用贝叶斯网络的条件独立 性进行严格推理，将知识表示和知识推理相结合，把健壮社团检测问题映射为不确定知识的 表达和推理问题。然后构造贝叶斯网络，根据节点的度信息确定贝叶斯网络相关参数（即各 个节点的条件概率