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

详细信息    查看全文

• 作者：Foad Mahdavi Pajouh ; Esmaeel Moradi…
• 关键词：2 ; club ; Graph ; based data mining ; Conditional value ; at ; risk ; Benders decomposition
• 刊名：Annals of Operations Research
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：249
• 期：1-2
• 页码：55-73
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Operation Research/Decision Theory; Combinatorics; Theory of Computation;
• 出版者：Springer US
• ISSN：1572-9338
• 卷排序：249

文摘

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.