论文部分内容阅读
近年来,随着Web2.0的发展,社会网络越来越受到更多学者们的关注和研究。在社会网络的众多性质中,社团结构是其最重要同时也是最具有研究意义的性质之一。通过社团的划分,我们不仅能够了解和分析网络的结构特点,也能够挖掘出表面数据关系之中的隐性信息。在目前的研究中已经有了很多经典的社团划分算法,比如Girvan-Newman算法,Keinighan-Lin算法等,但是准确度和时间复杂度之间的平衡仍然是社团划分算法的主要问题之一。本文对社会网络的社团划分方法进行了研究,首先系统地分析比较了现有划分算法的优缺点,然后基于聚类分析的思想,提出了两种改进的社团划分方法:基于节点相似度系数聚类的社团划分方法(Community Division Method Based on Node Similarity Clustering,NSCCDM)和基于遗传算法聚类的社团划分方法(Genetic Algorithm Clustering Based Community Division Method,GACCDM)。NSCCDM方法首先通过欧几里得公式和最短路径构造了一种新的相似度系数度量方法,并生成相似度系数矩阵,然后通过比较节点之间的相似度系数,进行节点的聚类,最后再使用模块度函数Q对被重复划分的节点进行最优社团选择。GACCDM方法主要采用了遗传算法的思想。该方法使用了模块度函数Q作为适应度函数来控制遗传算法的进化过程;采用指向性的变异策略代替随机变异策略加快算法的收敛速度;并结合网络的拓扑结构和节点之间的相似度系数关系进行遗传聚类,从而完成对社团的划分。本文使用java语言对以上的两种方法进行编码实现,并将它们分别应用于真实社会网络:Zachary空手道俱乐部网络、海豚网络以及美国足球网络。实验得出的划分结果与实际情况相符,从而表明了本文算法的准确性和可用性。