An exact algorithm for the maximum probabilistic clique problem

Zhuqi Miao, Balabhaskar Balasundaram, Eduardo L. Pasiliao

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

Original languageEnglish
Pages (from-to)105-120
Number of pages16
JournalJournal of Combinatorial Optimization
Volume28
Issue number1
DOIs
StatePublished - 1 Jan 2014
Externally publishedYes

Fingerprint

Exact Algorithms
Clique
Maximum Clique Problem
Testbed
Combinatorial optimization
Electric network analysis
Data mining
Combinatorial Algorithms
Sampling
Biological Networks
Combinatorial Optimization
Network Analysis
Social Networks
Cardinality
Data Mining
Subset
Graph in graph theory
Range of data

Keywords

  • Branch-and-bound
  • Maximum clique problem
  • Probabilistic clique
  • Probabilistic programming

Cite this

Miao, Zhuqi ; Balasundaram, Balabhaskar ; Pasiliao, Eduardo L. / An exact algorithm for the maximum probabilistic clique problem. In: Journal of Combinatorial Optimization. 2014 ; Vol. 28, No. 1. pp. 105-120.
@article{aed59629a7f745b3847b9cbcc64aa877,
title = "An exact algorithm for the maximum probabilistic clique problem",
abstract = "The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.",
keywords = "Branch-and-bound, Maximum clique problem, Probabilistic clique, Probabilistic programming",
author = "Zhuqi Miao and Balabhaskar Balasundaram and Pasiliao, {Eduardo L.}",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/s10878-013-9699-4",
language = "English",
volume = "28",
pages = "105--120",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "1",

}

An exact algorithm for the maximum probabilistic clique problem. / Miao, Zhuqi; Balasundaram, Balabhaskar; Pasiliao, Eduardo L.

In: Journal of Combinatorial Optimization, Vol. 28, No. 1, 01.01.2014, p. 105-120.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An exact algorithm for the maximum probabilistic clique problem

AU - Miao, Zhuqi

AU - Balasundaram, Balabhaskar

AU - Pasiliao, Eduardo L.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

AB - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.

KW - Branch-and-bound

KW - Maximum clique problem

KW - Probabilistic clique

KW - Probabilistic programming

UR - http://www.scopus.com/inward/record.url?scp=84903594187&partnerID=8YFLogxK

U2 - 10.1007/s10878-013-9699-4

DO - 10.1007/s10878-013-9699-4

M3 - Article

AN - SCOPUS:84903594187

VL - 28

SP - 105

EP - 120

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 1

ER -