期刊文献+

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

FINDING K DENSE SUBGRAPHS WITH LIMITED OVERLAP IN COMPLEX NETWORK
下载PDF
导出
摘要 密集子图问题广泛应用于社区发现、生物信息学中基因共表达和蛋白质相互作用等方面,是图挖掘和复杂网络研究的一个重要环节。现有的研究大多围绕查找单个密集子图和多个不相交的密集子图展开,忽略了子图的重叠及子图间的联系。为填补这一空白,引入最小密集图的概念,提出查找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.
出处 《计算机应用与软件》 CSCD 2016年第12期140-144,147,共6页 Computer Applications and Software
基金 南京财经大学研究生创新研究基金项目(YJS14102)
关键词 密集子图 复杂网络 平均度 线性规划 Dense subgraph Complex network Average degree Linear programming
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部