论文部分内容阅读
复杂网络可以用来描述交通网、互联网、社交关系网络、神经网络以及科研合作网络等现实网络。随着对复杂网络研究的深入,研究者们发现社区结构存在于很多的现实网络中,并且现实生活中很多社区之间存在相互关联和彼此重叠。基于此我们主要对复杂网络中社区的发现及划分进行研究。复杂网络是由节点和边构成,网络中的节点代表不同实体,可以同时属于多个社区;边表示实体之间的某种关系。在划分社区时可根据节点邻居属性划分其所属社区,本文基于节点邻居的多样性及节点选取的随机性主要做了以下工作:1)提出复杂网络重叠社区结构划分的个体从众演化算法ICEA(Individual Conformity Evolutionary Algorithm)。算法根据社区节点的从众和变异属性,使得在划分社区时根据节点的邻居不同从而产生不同的社区划分结果,通过比较模块度找到比较好的社区划分,在社区结构确定的基础上我们使用陈俊宇等人的邻居投票机制LM-NV(Louvain Method with Neighbor Voting)对社区的边界节点进行判断,判断其是否为重叠节点,从而完成复杂网络重叠社区的划分工作。2)提出一种基因片段覆盖算法GFCA(Gene Fragment Covering Algorithm),基本思想是将由节点邻居组成的个体,随机选取其它个体的一个基因片段覆盖到当前个体的相应位置上,若覆盖后,模块度有改善,则选择覆盖后的个体作为当前个体;否则保留原来的个体。在真实网络上进行实验,结果表明此算法具有一定的优势及实际可用性。为了验证所提算法ICEA和GFCA社区划分的有效性,我们选取常用于测试复杂网络划分算法的三个真实数据集Zachary Karate club、Dolphin Social network以及American College football对两个算法进行了测试,并将我们的算法与Newman的GN算法和快速算法FN、基于改进的K-means模糊聚类的网络社区结构划分算法NKFCM以及基于粒子群算法的模糊社区结构划分算法PFCM在划分社区的模块度、划分社区个数以及迭代次数几个方面进行对比分析。实验结果表明本文所提算法ICEA和GFCA在运行时间和划分结果等方面都优于典型算法。