Search

Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold τ > 0 , the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges so that each clique's weight is bounded above by τ . Clusters composed of important actors with quick communications can be effectively modeled as large-weight cliques in real-world settings such as social, communication, and biological systems. Here, we prove that EBCP is NP-hard even when τ is a fixed parameter, and propose a combinatorial lower bound for its optimal objective. A class of inequalities that are valid for the set of feasible solution to EBCP is identified, and sufficient conditions for these inequalities to induce facets are presented. Using this class of inequalities, EBCP is formulated as a linear 0–1 program including potentially exponential number of constraints. We develop the first problem-specific branch-and-cut algorithm to solve EBCP, which utilizes the aforementioned constraints in a lazy manner. We also developed the first combinatorial branch-and-bound solution approach for this problem, which aims to handle large graph instances. Finally, computational results of solving EBCP on a collection of random graphs and power-law real-world networks by using our proposed exact algorithms are also provided. [ABSTRACT FROM AUTHOR]

Detecting large 2-clubs in biological, social and financial networks can help reveal important information about the structure of the underlying systems. In large-scale networks that are error-prone, the uncertainty associated with the existence of an edge between two vertices can be modeled by assigning a failure probability to that edge. Here, we study the problem of detecting large 'risk-averse' 2-clubs in graphs subject to probabilistic edge failures. To achieve risk aversion, we first model the loss in 2-club property due to probabilistic edge failures as a function of the decision (chosen 2-club cluster) and randomness (graph structure). Then, we utilize the conditional value-at-risk (CVaR) of the loss for a given decision as a quantitative measure of risk for that decision, which is bounded in the model. More precisely, the problem is modeled as a CVaR-constrained single-stage stochastic program. The main contribution of this article is a new Benders decomposition algorithm that outperforms an existing decomposition approach on a test-bed of randomly generated instances, and real-life biological and social networks. [ABSTRACT FROM AUTHOR]

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem. [ABSTRACT FROM AUTHOR]

Graph clustering (partitioning) is a helpful tool in understanding complex systems and analyzing their structure and internal properties. One approach for graph clustering is based on partitioning the graph into cliques. However, clique models are too restrictive and prone to errors given imperfect data. Thus, using clique relaxations instead may provide a more reasonable and applicable partitioning of the graph. An s-club is a distance-based relaxation of a clique and is formally defined as a subset of vertices inducing a subgraph with a diameter of at most s. In this work, we study the minimum s-club partitioning problem, which is to partition the graph into a minimum number of non-overlapping s-club clusters. Integer programming techniques and combinatorial branch-and-bound framework are employed to develop exact algorithms to solve this problem. We also study and compare the computational performance of the proposed algorithms for the special cases of s = 2 and s = 3 on a test-bed of randomly generated instances and real-life graphs. [ABSTRACT FROM AUTHOR]