在复杂网络中查找k个有限重叠的密集子图

FINDING K DENSE SUBGRAPHS WITH LIMITED OVERLAP IN COMPLEX NETWORK

密集子图问题广泛应用于社区发现、生物信息学中基因共表达和蛋白质相互作用等方面,是图挖掘和复杂网络研究的一个重要环节。现有的研究大多围绕查找单个密集子图和多个不相交的密集子图展开,忽略了子图的重叠及子图间的联系。为填补这一空白,引入最小密集图的概念,提出查找k个有限重叠的密集子图问题,最大化总密度的同时,满足子图节点集合间不超过限定的Jaccard系数。提出两个启发式算法,并通过实例计算以及与现有算法的比较分析,证明了算法的有效性。

Dense subgraph has wide applications such as community detection, gene co-expression and protein-protein interactions in bioinformatics, etc. , and is a key link in graph mining and complex network research. Most of current researches are expanded surrounding either finding a single dense subgraph or finding multiple disjoint subgraphs, but ignore subgraphs＇ overlap and the connection between subgraphs. To fill the gap, in this work we introduced the concept of minimal dense subgraph and proposed the issue of finding k dense subgraphs with limited overlap, while maximising the total density, it satisfies the Jaccard coefficient without exceeding the limitation between the sets of nodes of subgraphs.＂ We proposed two heuristic algorithms, and proved the effectiveness of our algorithm through example calculation and comparative analysis on existing algorithms.