Optimizing network robustness by edge rewiring: a general framework

详细信息    查看全文

• 作者：Hau Chan ; Leman Akoglu
• 刊名：Data Mining and Knowledge Discovery
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：30
• 期：5
• 页码：1395-1425
• 全文大小：980 KB
• 刊物类别：Computer Science
• 刊物主题：Data Mining and Knowledge Discovery
  Computing Methodologies
  Artificial Intelligence and Robotics
  Statistics
  Statistics for Engineering, Physics, Computer Science, Chemistry and Geosciences
  Information Storage and Retrieval
  
• 出版者：Springer Netherlands
• ISSN：1573-756X
• 卷排序：30

文摘

Spectral measures have long been used to quantify the robustness of real-world graphs. For example, spectral radius (or the principal eigenvalue) is related to the effective spreading rates of dynamic processes (e.g., rumor, disease, information propagation) on graphs. Algebraic connectivity (or the Fiedler value), which is a lower bound on the node and edge connectivity of a graph, captures the “partitionability” of a graph into disjoint components. In this work we address the problem of modifying a given graph’s structure under a given budget so as to maximally improve its robustness, as quantified by spectral measures. We focus on modifications based on degree-preserving edge rewiring, such that the expected load (e.g., airport flight capacity) or physical/hardware requirement (e.g., count of ISP router traffic switches) of nodes remain unchanged. Different from a vast literature of measure-independent heuristic approaches, we propose an algorithm, called EdgeRewire, which optimizes a specific measure of interest directly. Notably, EdgeRewire is general to accommodate six different spectral measures. Experiments on real-world datasets from three different domains (Internet AS-level, P2P, and airport flights graphs) show the effectiveness of our approach, where EdgeRewire produces graphs with both (i) higher robustness, and (ii) higher attack-tolerance over several state-of-the-art methods.KeywordsGraph robustnessEdge rewiringRobustnesss measures Graph spectrumOptimization algorithmsAttack tolerance