TY - JOUR
T1 - Detecting large risk-averse 2-clubs in graphs with random edge failures
AU - Mahdavi Pajouh, Foad
AU - Moradi, Esmaeel
AU - Balasundaram, Balabhaskar
N1 - Publisher Copyright:
© 2016, Springer Science+Business Media New York.
PY - 2017/2/1
Y1 - 2017/2/1
N2 - 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.
AB - 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.
KW - 2-club
KW - Benders decomposition
KW - Conditional value-at-risk
KW - Graph-based data mining
UR - http://www.scopus.com/inward/record.url?scp=84982854004&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84982854004&partnerID=8YFLogxK
U2 - 10.1007/s10479-016-2279-0
DO - 10.1007/s10479-016-2279-0
M3 - Article
AN - SCOPUS:84982854004
SN - 0254-5330
VL - 249
SP - 55
EP - 73
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 1-2
ER -