Detecting large risk-averse 2-clubs in graphs with random edge failures

Foad Mahdavi Pajouh (), Esmaeel Moradi () and Balabhaskar Balasundaram ()
Additional contact information
Foad Mahdavi Pajouh: University of Massachusetts Boston
Esmaeel Moradi: Lee Scott Logistics Complex
Balabhaskar Balasundaram: Oklahoma State University

Annals of Operations Research, 2017, vol. 249, issue 1, No 5, 55-73

Abstract: Abstract 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.

Keywords: 2-club; Graph-based data mining; Conditional value-at-risk; Benders decomposition (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2279-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:249:y:2017:i:1:d:10.1007_s10479-016-2279-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2279-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().