基于图论方法的符号网络中重叠聚类算法的研究

项目名称： 基于图论方法的符号网络中重叠聚类算法的研究

项目编号： No.11401346

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 亓兴勤

作者单位： 山东大学

项目金额： 22万元

中文摘要： 类簇结构或社区结构是复杂网络最普遍和最重要的拓扑结构属性之一。目前已有的聚类算法大多是基于非符号复杂网络（边上权重为正），对符号网络（signed network）（边上权重扩展为正、负）的研究少之又少。本项目利用图论技术，基于申请人在非符号复杂网络已有聚类算法的基础上，通过寻找稠密子图和收缩子图的方法，对符号网络的类簇结构进行研究，设计一个高效精确的层次聚类算法，并结合申请人在复杂网络核心节点寻找问题上已有结果，利用每个子类簇内核心节点的个数，对初始聚类结果进行二次迭代，提高算法精确性。该项目的研究，将解决目前符号网络聚类算法中存在的“无法实现一个对象可属于多个类簇的重叠聚类”和“类簇个数需要用户事先给定”这两个主要问题。本项目的研究结果可以广泛应用于社会网络分析（例如恐怖组织识别等），生物网络分析（例如蛋白质交互网络分析和未知蛋白质功能预测等）以及Web社区挖掘和文档聚类等众多领域。

中文关键词： 符号网络；社团结构；图论；节点重要性；算法

英文摘要： Network community structure or network cluster structure is one of the most fundamental and important topological properties of complex networks, as well as the other two properties “small world” and “scale-free”. Complex networks can be modeled as graphs

英文关键词： signed network；community structure；graph theory；vertex centrality；algorithm