  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)
utilize a discrete link structure, complex systems must be transformed to this
representation in order to investigate network properties. However, in many
domains there may be uncertainty about the relationship structure and any
uncertainty information would be lost in translation to a discrete
representation. Uncertainty may arise in domains where there is moderating link
information that cannot be easily observed, i.e., links become inactive over
time but may not be dropped or observed links may not always corresponds to a
valid relationship. In order to represent and reason with these types of
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 three real-world networks from
Enron, Facebook, and DBLP, showing that our proposed methods more accurately
capture salient effects without being susceptible to local noise, and that the
resulting analysis produces a better understanding of the graph structure and
the uncertainty resulting from its change over time.
