论文标题
OCSM：找到最低度的重叠的内聚子图
OCSM : Finding Overlapping Cohesive Subgraphs with Minimum Degree
论文作者
论文摘要
网络中有凝聚力的子图发现是基本问题之一，并进行了数十年的调查。在本文中，我们提出了具有最小程度（OCSM）问题的重叠的内聚子图，该子图结合了OCSM的三个关键概念：（i）基于边缘的重叠，（ii）最小程度约束和（iii）图形密度。据我们所知，这是第一项通过结合图密度来识别最低限制性子图的第一项工作。由于OCSM问题是NP-HARD，因此我们提出了两种算法：高级剥离算法和基于种子的扩展算法。最后，我们通过现实世界网络展示了实验研究，以证明我们提出的算法的有效性和效率。
Cohesive subgraph discovery in a network is one of the fundamental problems and investigated for several decades. In this paper, we propose the Overlapping Cohesive Subgraphs with Minimum degree (OCSM) problem which combines three key concepts for OCSM : (i) edge-based overlapping, (ii) the minimum degree constraint, and (iii) the graph density. To the best of our knowledge, this is the first work to identify overlapping cohesive subgraphs with minimum degree by incorporating the graph density. Since the OCSM problem is NP-hard, we propose two algorithms: advanced peeling algorithm and seed-based expansion algorithm. Finally, we show the experimental study with real-world networks to demonstrate the effectiveness and efficiency of our proposed algorithms.
