大规模复杂网络社区发现算法研究

作     者：郭京津 

作者单位：河北工业大学 

学位级别：硕士

导师姓名：顾军华

授予年度：2018年

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：社区发现 蚁群算法 社区重建 挖掘所有团结构 复杂网络 

摘      要：现实世界中的很多相互关系都可以用复杂网络的形式进行描述,如社交关系网络、信息通信网络、蛋白质结构网络、论文合著网络等。如何挖掘出这些网络中隐含的信息成为学术研究的热点,其中社区结构是复杂网络中最重要的拓扑属性。对复杂网络进行社区发现可以更加深入的了解网络的内部结构、网络属性和相互关系。对社会学、生物医学、物理学、计算科学等学科的理论研究有着重要的推动意义。随着信息技术的高速发展,网络的节点规模增大和结构更为复杂,现有的算法主要是基于整体网络的社区发现,需要进行全局的遍历,对于大规模复杂网络,遍历网络所需的时间消耗较大。因此本课题采用子网络结构作为大规模复杂网络社区发现的切入点,通过简化网络的规模来提高算法的计算效率,提出一种基于蚁群算法和模块度优化的社区发现算法(Community discovery algorithm based on ant algorithm and modularity optimization-AMCA)。首先,本文先求解复杂网络的所有团作为子网络结构。然后,将求得的子网络结构作为新的节点,对大规模复杂网络进行网络结构重建,缩减原网络的规模。最后,提出一种基于多重合并的模块度优化算法求解社区。本文的主要研究工作包括以下三部分:1)提出了一种改进的蚁群算法(Improved ant colony algorithm-IACO)来求解网络的所有团结构,通过预先的求解所有团结构,缩减复杂网络的规模,克服因为大规模复杂社会网络中节点较多造成的求解速度较慢问题,同时保证了数据的独立性。2)提出一种网络结构重建算法(Network structure reconstruction algorithm-NSRA),将求得的所有团结构作为新的节点,重新构建团结点之间的边结构,从而缩小网络规模,均衡复杂社会网络的网络结构,减少社区发现阶段的算法负载。3)提出了一种多重合并的模块度优化算法(Based on the merge module optimization algorithm-MMOA),用于求解重构网络中的社区结构。最后在多个大规模复杂网络数据集上,与三种目前实验效果较好的社区发现算法进行对比,结果验证了本文提出的算法在求解质量和求解效率等方面都取得了一定的效果。