论文部分内容阅读
复杂网络能够将真实世界中广泛存在的复杂系统用网络的形式表示出来，例如社交网络、生物网络、交通网络等。对该领域的研究，不仅吸引了大量来自管理科学、计算机科学和物理学等领域科研人员的广泛关注，也引起了社会学、生物学等学科学者们极大的研究兴趣，复杂网络研究已经成为一个重要的多学科交叉研究热点领域。同时，由于大数据技术的迅速发展，获取和深入挖掘网络数据成为可能。大量的研究表明，复杂网络中存在社团结构，具有社团内部节点间连接紧密，社团之间的节点间连接稀疏的特点。社团探测(community detection)，也被称为社团发现、社团识别、社团挖掘等。进行社团探测的目的就在于发现网络中真实存在的社团结构，以助于深入理解网络中社团内部个体和不同社团之间个体的关系，同时也为研究网络中其他的性质和功能提供基础。
近些年，有许多不同类型的社团探测算法被提出，主要基于模块度优化、随机概率模型、谱理论以及马尔可夫动力学等方法。随着网络规模越来越大，以及社团结构的广泛应用，对社团探测算法的精度和效率都提出了更高的要求；又由于节点角色的多样化，以及隶属关系的多重性，非重叠社团划分已经不能满足于某些特定的需求，因而如何设计算法快速而精确的发现重叠社团结构，也是亟待解决的问题之一。因此，本文从网络的局部拓扑结构出发，深入研究网络拓扑结构，分别针对非重叠和重叠社团的探测算法设计及应用方面进行研究，做出如下工作：
首先，深入分析网络局部拓扑特征，提出衡量节点相似性的指标，利用节点相似性原理，快速挖掘连接紧密的节点集，为获得精确社团探测结果提供了科学合理的预划分方法。根据对节点相似性程度的要求不同，能够探测出连接紧密程度不同的节点集，并在此基础上进行优化来获得最优解。在网络预划分结果优化阶段，分别从局部拓扑融合优化和全局多目标函数优化两方面进行研究，提出了基于分割-凝聚(DA)的二阶段社团探测算法和网络预压缩下基于多目标进化算法的社团发现机制(Com-MOEA/D)。在DA算法的凝聚阶段，分析局部网络拓扑，设计社团吸引力指标，融合模块度函数进行优化。大量的真实网络和计算机生成网络上的实验结果表明，DA算法具有较高的精度，尤其是在社团结构较为模糊时。此外，DA算法能够在自我中心网络中表现出优势。针对节点相似性程度的要求不同，Com-MOEA/D算法提出了节点相似度阈值参数，并将连接紧密的节点集压缩成一个超级节点，从而缩减了原网络的规模，形成了带有自环结构的压缩网络。在针对压缩网络的社团探测过程中，采用了基于分解的多目标进化算法来求解，多个目标函数的综合考量能够带来一组社团探测的结果。可以根据不同的目标函数来选择一个最优解。实验结果也验证了本算法的有效性。
其次，针对网络中节点角色的多样性，每个节点可能隶属于多个社团结构的要求，提出一种基于社团中的核心结构进行局部扩张和调整的重叠社团探测算法CoreOCD。该算法的基本思想是首先寻找网络中的核心团结构来替代大部分算法中的种子节点，然后在核心团结构的基础上，根据每个节点的局部拓扑信息设计了节点加入意愿指标，按照该指标值的大小进行局部社团的迅速扩张；随后，对局部扩张阶段所获得的社团结构进行边界节点的调整，并根据节点在相应社团中的贡献而设计了节点的隶属度系数，通过隶属度系数的大小进行节点微调。本算法在局部扩张时并没有采用传统的全局网络适应性函数，而直接按照加入意愿指标进行扩张，提高了效率；然后在调整阶段根据节点的贡献去进行结果的微调，增加了结果的准确性。
最后，将社团划分的结果应用于传染病接触网络中的疾病传播免疫策略的设计。社团结构在疾病传播、消息传播以及推荐系统等各个方面都有广泛的应用，尤其是在疾病传播过程中，社团内部的病毒传播速度较快，社团之间的传播速度稍慢，需要依赖桥节点的帮助。因此，本文将目标免疫节点的选择建模成优化问题，设计了基于遗传算法的优化算法。为了更精确、快速的获得目标免疫节点集，在构建候选节点集时选取了社团内的部分关键节点以及桥节点，能够缩减候选集规模。实验结果表明本策略是非常有效的。
近些年，有许多不同类型的社团探测算法被提出，主要基于模块度优化、随机概率模型、谱理论以及马尔可夫动力学等方法。随着网络规模越来越大，以及社团结构的广泛应用，对社团探测算法的精度和效率都提出了更高的要求；又由于节点角色的多样化，以及隶属关系的多重性，非重叠社团划分已经不能满足于某些特定的需求，因而如何设计算法快速而精确的发现重叠社团结构，也是亟待解决的问题之一。因此，本文从网络的局部拓扑结构出发，深入研究网络拓扑结构，分别针对非重叠和重叠社团的探测算法设计及应用方面进行研究，做出如下工作：
首先，深入分析网络局部拓扑特征，提出衡量节点相似性的指标，利用节点相似性原理，快速挖掘连接紧密的节点集，为获得精确社团探测结果提供了科学合理的预划分方法。根据对节点相似性程度的要求不同，能够探测出连接紧密程度不同的节点集，并在此基础上进行优化来获得最优解。在网络预划分结果优化阶段，分别从局部拓扑融合优化和全局多目标函数优化两方面进行研究，提出了基于分割-凝聚(DA)的二阶段社团探测算法和网络预压缩下基于多目标进化算法的社团发现机制(Com-MOEA/D)。在DA算法的凝聚阶段，分析局部网络拓扑，设计社团吸引力指标，融合模块度函数进行优化。大量的真实网络和计算机生成网络上的实验结果表明，DA算法具有较高的精度，尤其是在社团结构较为模糊时。此外，DA算法能够在自我中心网络中表现出优势。针对节点相似性程度的要求不同，Com-MOEA/D算法提出了节点相似度阈值参数，并将连接紧密的节点集压缩成一个超级节点，从而缩减了原网络的规模，形成了带有自环结构的压缩网络。在针对压缩网络的社团探测过程中，采用了基于分解的多目标进化算法来求解，多个目标函数的综合考量能够带来一组社团探测的结果。可以根据不同的目标函数来选择一个最优解。实验结果也验证了本算法的有效性。
其次，针对网络中节点角色的多样性，每个节点可能隶属于多个社团结构的要求，提出一种基于社团中的核心结构进行局部扩张和调整的重叠社团探测算法CoreOCD。该算法的基本思想是首先寻找网络中的核心团结构来替代大部分算法中的种子节点，然后在核心团结构的基础上，根据每个节点的局部拓扑信息设计了节点加入意愿指标，按照该指标值的大小进行局部社团的迅速扩张；随后，对局部扩张阶段所获得的社团结构进行边界节点的调整，并根据节点在相应社团中的贡献而设计了节点的隶属度系数，通过隶属度系数的大小进行节点微调。本算法在局部扩张时并没有采用传统的全局网络适应性函数，而直接按照加入意愿指标进行扩张，提高了效率；然后在调整阶段根据节点的贡献去进行结果的微调，增加了结果的准确性。
最后，将社团划分的结果应用于传染病接触网络中的疾病传播免疫策略的设计。社团结构在疾病传播、消息传播以及推荐系统等各个方面都有广泛的应用，尤其是在疾病传播过程中，社团内部的病毒传播速度较快，社团之间的传播速度稍慢，需要依赖桥节点的帮助。因此，本文将目标免疫节点的选择建模成优化问题，设计了基于遗传算法的优化算法。为了更精确、快速的获得目标免疫节点集，在构建候选节点集时选取了社团内的部分关键节点以及桥节点，能够缩减候选集规模。实验结果表明本策略是非常有效的。