论文摘要
客观世界中的许多系统都由一些相互联系的实体所组成。而网络提供了一种抽象的形式来描述这类系统。随着信息技术的发展,人们有更强的能力去观察客观世界并且将观察结果记录为数据。于是,各种各样的网络数据大量涌现,如万维网、在线社会网络、论文引用网络、科研合作网络等等。社区发现和网络数据分类是在网络数据上挖掘隐含信息的重要技术之一,其实质就是基于网络中的链接对节点进行聚类和分类。它在研究网络的功能组成、实体聚类与分类以及网络数据存储等方面有着广泛的应用。近几年来,社区发现和网络数据分类问题受到研究人员的广泛关注,一些解决方法相继提出。然而,现有的方法并不是在所有类型的网络数据上都能够取得良好的效果。例如,基于模块度优化的社区发现方法可能会在一些没有任何社区结构的网络上也能发现社区结构;基于同质性假设的网络数据分类方法在低同质性网络上分类精度较低。概率生成模型可以依据模型假设对数据进行建模,然后通过统计推测的方法将模型拟合到现实数据上,从而推测出现实数据的潜在特征。所以基于概率生成模型的方法只依赖于模型假设和实际数据,它具有极大的灵活性,采用不同的模型假设可以适应不同类型的数据。因此,本文运用这一技术,以提高社区发现和网络数据分类的准确性为目标,对社区发现和网络数据分类问题进行深入地研究,取得了如下成果:(1)提出基于节点社区模型的非重叠社区发现方法。从节点社区的思想出发,认为社区由节点组成并且一个节点只属于一个社区,用非参数化方法对网络和节点的社区建立概率生成模型。该模型的基本思想是:节点与另一个节点之间有边相连,是因为这个节点所在的社区想要同另一个节点相连接。通过吉布斯采样方法求解模型中的潜在变量,可以计算每个节点的社区。由于采用了非参数化方法,所以社区个数可以在模型求解的过程中自动确定。通过人造网络和真实网络上的实验表明此方法是一个有效的非重叠社区发现方法。(2)提出了基于边社区模型的重叠社区发现方法。从边社区思想出发,认为社区是由边所组成的,对网络和边的社区建立概率生成模型。利用非参数化方法来求解模型参数;并且利用模型参数计算出节点属于每个社区的概率,从而发现网络中的社区。由于采用了边社区思想,使得一个节点可以属于多个社区。此外,非参数化的模型求解过程,使得社区个数可以在模型求解的过程中自动确定。人造网络和真实网络上的实验表明此方法能够有效地发现网络中的重叠社区。此外,此方法不仅可以发现节点的所属社区,还能计算出它在每个社区的参与程度。(3)提出了基于概率生成模型的网络数据分类方法。针对低同质性网络的特点,提出节点的类别传播分布的概念并且用它来描述低同质性网络中两个节点相连的概率。在此基础上,提出了基于类别传播分布的网络概率生成模型。在模型中将被分类节点的类别作为潜在变量,网络的边和已知类别节点的类别作为观察数据,通过将模型拟合到观察数据上,计算出潜在变量的取值,从而得到被分类节点的类别。在真实网络数据上的实验表明此方法在低同质性网络上有更好的分类性能。(4)针对网络以及节点社区和类别的可视化展示问题,开发了一个基于节点属性的网络可视化工具:ADraw。在节点布局上,ADraw采用基于属性的多阶段聚类布局算法,该算法除了满足一般聚类布局中同类节点相互靠近的要求外,还增加了“拥有多个属性取值的节点应该位于相应的单个属性取值节点群之间”这一布局准则。在节点着色上,ADraw采用包含不同颜色扇形块的饼图来表示拥有多个属性取值的节点。用基于属性的节点着色算法计算扇形块的位置,该算法保证“扇形块尽可能地靠近有相同颜色的节点群”。