Evolutionary Approach for Detecting Significant Edges in Social and Communication Networks

Abstract

Detection of significant edges maintaining the connectivity in complex networks is essential in many applications such as attack vulnerability analysis, the spread of epidemic diseases, and information spreading patterns discovery. There are many existing methods enabling us to evaluate the criticality ranking of links in networks, which are based on straightforward algorithms and topological features of analyzed graphs. In this paper, we offer another perspective on the problem and propose a novel approach, to be called the Evolutionary Approach (EA), that is based on a genetic-like algorithm and turns directly to an integral criterion of decomposition efficiency instead of network topology. Like all the genetic algorithms, EA is grounded on the iterative enhancement of randomly generated solutions via reproduction, cross-over, and mutation processes. The EA-efficiency is illustrated via decomposing three real-world benchmark networks by using the proposed method, the acknowledged Link Entropy (LE) method, and the most recent Improved Link Entropy (ILE) method. The comparison of the obtained results demonstrates that the EA-efficiency exceeds the ILE-efficiency for 5.7%–28.1% depending on the network complexity, with respect to the LE-efficiency the increase is approximately two-fold. Besides, the temporal aspects of ordering the network edges according to their significance using solely EA or in its combination with LE and ILE are discussed.

Keywords

• Complex networks
• critical edges
• evolutionary approach
• improved link entropy
• link entropy