Identifying influential edges in a directed network: big events, upsets and non-transitivity

Networks model complex systems from a wide range of applications. Methods that extract information from such systems are important tools in such fields of study. One of the well-studied aspects of a network is the concept of the most influential or powerful node in the network. The edges of a graph can exert great influence in such measures of nodal power. In this paper, we propose methods that identify influential <it>edges</it> in a network. The paper uses the proposed methods to analyse two networks from disparate applications—win–loss data of teams competing in the 2011 season of NCAA Football Bowl Subdivision and the 2001 Enron employee email dataset. Several edge measures are proposed. The first set of measures adapt node measures to the context of analysing the importance of edges. The second set include measuring betweenness, rank sensitivity to perturbations in the network and the sensitivity of the ranking as measured by a linear programme formulation. The methods are applied to the aforementioned networks and the benefits and appropriateness of the methods are discussed and contrasted.