Methods to Determine Node Centrality and Clustering in Graphs with Uncertain Structure

Abstract

Much of the past work in network analysis has focused on analyzing discrete graphs, where binary edges represent the “presence” or “absence” of a relationship. Since traditional network measures (e.g., betweenness centrality) assume a discrete link structure, data about complex systems must be transformed to this representation before calculating network properties. In many domains where there may be uncertainty about the relationship structure, this transformation to a discrete representation will result in a lose of information. In order to represent and reason with network uncertainty, we move beyond the discrete graph framework and develop social network measures based on a probabilistic graph representation. More specifically, we develop measures of path length, betweenness centrality, and clustering coefficient— one set based on sampling and one based on probabilistic paths. We evaluate our methods on two real-world networks, Enron and Facebook, showing that our proposed methods more accurately capture salient effects without being susceptible to local noise.