近年来,在不同领域、广泛多样的系统中,图变成了一种极其有用的描述工具,生物,社会,技术和信息网络等许多领域的系统都能建模为图(网络)来研究。为了理解网络系统的特征,网络分析研究就变得非常重要。对网络的研究从最初的规则网络,到随机网络,到近几年的复杂网络,越来越多关于网络的研究工作持续开展。无标度网络的发现,使人类对于复杂网络系统有了全新的认识。在这样的网络中,顶点度的分布显示出很大的不均匀性,同时,表现出高水平的秩序和组织,特点是网络中顶点度的分布非常广泛,大量低度数的顶点围绕少量高度数的顶点共存,网络呈现出社区结构(也称为簇或模块)。社区发现在社会学、生物学和计算机科学等学科中都有重要应用,如提高网络服务质量、增强网络销售、发现有共同兴趣的科学家小组、揭示政府组织运行方式、发现动物的社会组织结构、聚类功能基因等等。近年,关于社区发现的很多新概念和新方法被提出来。在无权图研究方面：模块度的提出极大促进该方向的研究,基于模块度优化的社区发现方法成为了主流方法,但现有模块度定义在一些应用背景下存在不足,有的模块度优化方法也存在缺陷。在带权图研究方面：针对带权图的工作相对来说比较少,权值本身的意义没有获得重视。而且,很多社会网络是基于交互行为建立的,交互的数量对社区结构有重要的影响。鉴于上述问题,为扩展社区发现算法的适应范围、提高发现社区的准确性、合理发现带权图中的社区结构,本文关注连接的度量问题,在模块度定义、改进社区发现算法、带权图社区发现等方面开展了研究工作。本文的主要研究内容和创新之处总结如下：(1)提出了基于耦合度的模块度。针对现有模块度在社区规模差异大和多社区情况下的不足,根据社区内部顶点间的连接相对紧密,社区之间的连接相对稀疏的特点。定义了社区间的连接密度和社区内的连接密度两个数值,通过二者之比定义了社区间祸合度,社区间连接越稀疏,社区内部越紧密,则社区耦合度越小。基于社区耦合度的定义,提出一种新的基于社区耦合程度的模块度,用来度量整个网络中社区划分质量。通过实验证实,该模块度既适用于社区大小相似的情形,也适用于社区大小差异较大的情形,并且在多社区的情况下,有比较合理的度量效果。(2)提出了一个非递归分裂的模块度优化社区发现算法。因递归二分过程的影响,分裂式模块度优化算法在多社区情况下存在划分结果可能不理想的问题。本文依据类似于k-均值聚类的思想,提出了一种基于模块度优化的社区发现算法。该算法根据指定的社区数目对网络进行初始划分,通过迭代移动社区内的顶点,完成网络的自组织,使得算法在当前社区数目已定的条件下,搜索到具有最大模块度的网络划分。随后,增大社区数目,重复上述过程,直至模块度减小或社区数目达到用户指定的最大数目k。算法中,每次对社区数目为n的初始划分都是在原始网络上进行,有效避免了递归二分引起的问题。实验表明,社区发现的效果良好。(3)基于成员交互行为,提出交互度的概念,并应用于层次凝聚社区发现算法。在描述交互关系的社会网络中,直观地认识到,顶点之间交互的强弱主要是包括两个方面：一是交互的绝对数量,二是交互的对等性。据此,提出了顶点交互度的概念,分析了网络拓扑结构对交互度的影响,引入概率中的可靠性概念,把顶点之间的交互度推广到社区之间的交互度。随后,以交互度作为层次凝聚算法的相似度指标,提出了基于交互度的层次凝聚社区发现算法,该算法能够比较自然地模拟社区的形成。实验表明,在带权图中能较好的发现合理的社区结构。(4)开发了一个社区发现的可视化工具软件Snviewer,提出了分层力导引算法。为了直观、高效地观察图和社区发现结果,基于JAVA平台,利用OpenGL图形编程接口,以力导引方法为布点算法,开发了一个可以动态演示图结构和社区发现结果的可视化工具。为了更好地显示社区发现结果,提出了分层力导引算法。另外,在动态布局过程中提供了人机交互机制,可以直观地人工干预布点过程,使布点结果更符合人们的观察习惯。
