论文部分内容阅读
网络社区发现是近些年计算机科学领域比较热门的研究课题,与此同时,不仅仅在计算机科学领域,自然科学和社会科学的其他领域或者分支方向内的专家学者们都对它进行着不懈的探索。从1736年欧拉给出哥尼斯堡七桥问题解法开始,科学家、数学家以及研究者们对图和它的性质的相关研究就一直在进行着,从未间断。自上个世纪30年代以来,对社会网络的研究一直是社会学领域研究的重要课题。在社区划分的各类算法中,大部分的算法都是在无权无向网络的基础上进行社区的划分,然而现实世界中的社会网络有一些是带权的和有向的,基于这样一个考虑,我们认为开展在带权值社会网络上的社区发现工作具有一定的实际意义,这在某种程度上也符合现实世界的客观需要和发展要求。本文所做的工作和主要的创新点如下所示:(1)首先,在当前基于带权值的社会网络上的社区发现研究并不多的情况下,以带权值的社会关系网络为研究对象,将网络社区内成员顶点之间的交互方向和交互权值考虑到社区划分的过程中;在交互度概念和度量方法的基础上,对社区划分结果度量的模块度方法进行改进,提出了交互模块度的概念、定义和计算公式,以此来对带权值的社会网络划分结果进行考量和评价。(2)根据交互模块度的定义和计算方法,设计了一个分裂式的基于贪心选择策略的社区发现算法。该算法设计的初衷是能够对带权值的社会网络结构进行社区发现工作,并根据交互模块度值的不同来寻找到最大的交互模块度值及其对应的划分结果。这个最大交互模块度值对应的划分即是与实际情形比较相符的划分,基本能够较好地反映真实的网络社区结构。(3)利用基于交互模块度设计的社区发现算法进行实验,在实际的带权值的社会关系网络上进行验证。我们分别在空手道俱乐部网络、海豚网络等带权值的网络上进行了验证,得到划分结果与实际的情形有一定的偏差,但是总体来说还是比较符合实际的网络社区结构的。实验表明,交互模块度能够较理想地对带权值的社会网络划分结果进行考量。本文中提出的基于带权值社会关系网络的IMC模块度能较好地度量划分出的社区与实际情况的吻合程度,并且在Zachary空手道俱乐部网络、海豚网络和Sade恒河猴网络上都进行了有效性的验证,这表明交互模块度在对带权值社会网络的划分结果进行衡量的工作中是有效的。我们能够利用交互模块度在有限的时间和步骤中根据贪心选择的策略寻找到近似最优的网络社区发现结果。