Authors:
Hélder Alves | FCUP, LIAAD INESC Tec | Portugal
Paula Brito | FEP, LIAAD INESC Tec | Portugal
Pedro Campos | FEP, LIAAD INESC Tec | Portugal
Keywords: interval-weighted networks, centrality measures, network flows.
The goal of social network analysis is to create, from raw relational data, a useful description of a system of relationships. These data can be described in the form of graphs or networks where vertices (or nodes) represent entities and edges (or links, arcs, etc.) represent relationships between pairs of entities.
A key issue in network analysis is the identification of the influence that certain nodes can exert over the others (Bonacich, 1987; Borgatti, 2005; Freeman, 1979). This centrality of nodes, or the place of a given entity (or actor) in the network, can be described using measures to determine the relative importance of these nodes within the network, namely: degree, closeness and betweenness (Freeman, 1979; Newman, 2004; Wasserman & Faust, 1994).
Network flow problems arise very frequently in real-life applications. In flow networks, the value of the connection linking two entities defines the capacity or the maximum amount that can be passed between them. This amount of flow that directly links adjacent points cannot exceed the capacity of that connection (Borgatti, 2005; Freeman, Borgatti, & White, 1991). Well known examples include communication and transportation networks, social networks, biological networks, etc. (Ahuja, Magnanti, & Orlin, 1993).
In classical graph theory, the flow capacity on an edge, c(e), is assumed to be constant (Freeman et al., 1991; Gómez, Figueira, & Eusébio, 2013). However, in real world applications, these capacities may vary within ranges rather than being constants (Jaulin, Kieffer, Didrit, & Walter, 2001; Moore, Kearfott, & Cloud, 2009). In this paper, to better model such variability on an edge, instead of using constants, we represent flow capacities as intervals (Hossain & Gatev, 2010; C. Hu & Hu, 2008; P. Hu, Dellar, & Hu, 2007). An interval representation of these flows (values) allows taking into account the variability observed in the original network, thereby minimizing the loss of information (Noirhomme-Fraiture & Brito, 2011).
Although several extensions of centrality measures to weighted networks have been proposed (Barrat & Barthelemy, 2004; Brandes, 2001; Newman, 2005; 2004; Opsahl, Agneessens, & Skvoretz, 2010), none takes into account the variability of link weights. To fill this gap, we extend these well-known metrics to the general case of interval-weighted networks. First, we introduce the Interval-Weighted Degree Centrality (IWDC), extending (Opsahl et al., 2010) Opshal ́s et al. (2010) concept of a tuning parameter to give relevance either to tie weights or number of ties alternatively. Secondly, based on network flows, where with each edge is assigned a flow which maximizes total flow between a pair of nodes and using Ford and Fulkerson (Ford & Fulkerson, 1962) max-flow method (Borgatti, 2005; Freeman et al., 1991), we present the Interval-Weighted Closeness Centrality (IWCC) and Interval-Weighted Betweenness Centrality (IWBC).
An application to a real interval-weighted network illustrates the proposed approaches.