.png){kind=icon}
.png){kind=icon}
Return
On the maximum small-world subgraph problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2019.07.042.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A clique (or a complete subgraph) is a popular model for an ideal cluster in a network. However, in many practical applications this notion turns out to be overly restrictive as it requires the existence of all pairwise links within the cluster. Thus, the researchers and practitioners often rely on various clique relaxation ideas for more flexible models of highly connected clusters. In this paper, we propose a new clique relaxation model referred to as a small-world subgraph, which represents a network cluster with small-world properties: low average distance and high clustering coefficient. In particular, we demonstrate that the proposed small-world subgraph model has better cohesiveness characteristics than other existing clique relaxation models in some worst-case scenarios. The main focus of the paper is on the problem of finding a small-world subgraph of maximum cardinality in a given graph. We describe a mixed integer programming (MIP) formulation of the problem along with several algorithmic enhancements. For solving large-scale instances of the problem we propose a greedy-type heuristic referred to as the iterative depth-first search (IDF) algorithm. Furthermore, we show that the small-world subgraphs identified by the IDF algorithm have an additional property that may be attractive from the practical perspective, namely, 2-connectivity. Finally, we perform extensive computational experiments on real-world and randomly generated networks to demonstrate the performance of the developed computational approaches that also reveal interesting insights about the proposed clique relaxation model. (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Networks
Combinatorial optimization
Integer programming
Clique relaxations
Network community detection
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
