Abstract
Traditional network analysis often treats relationships as binary, ignoring the temporal decay and inherent uncertainty of real-world interactions. This paper introduces a probabilistic framework to model "uncertain" graphs where edge existence is defined by a probability distribution. We propose novel methods for calculating node centrality and clustering coefficients, including a "Most Probable Path" (MLH) algorithm and a Taylor-expansion-based clustering estimate. Our evaluation on real-world datasets, such as the Enron email corpus, demonstrates that these probabilistic measures are more robust and less noisy than standard time-slice or aggregate methods, accurately capturing dynamic shifts in network influence.
Introduction
Most social network analysis relies on discrete, binary graphs. However, real-world relationships are rarely so simple; they vary in strength and decay over time. Researchers typically address this using either an "Aggregate Approach," which merges all historical data into a single dense graph, or a "Time-Slice Approach," which examines only recent windows of activity. Both methods have significant drawbacks: the aggregate approach fails to reflect current trends, while the time-slice approach is often too noisy. This paper bridges this gap by treating the graph as a probabilistic distribution where edge activity is determined by the frequency and recency of interactions.
Methodology
The authors propose two primary strategies for network measurement in uncertain environments:
- Sampling-based Measures: These treat the probabilistic graph as a population of possible discrete graphs. Expected values for centrality and path length are approximated via Monte Carlo sampling.
- Most Probable Paths (MLH): To reduce computational costs, a direct approach uses a modified Dijkstra’s algorithm to find the most probable path between nodes. A "Transmission Prior" ($\beta$) is introduced to model the probability of information successfully passing through a link, naturally penalizing longer paths.
- Probabilistic Clustering Coefficient: Instead of discrete triangle counting, a first-order Taylor expansion estimates the ratio of expected triangles to expected triples directly from edge probabilities.
Experimental Results
The methods were evaluated on the Enron email dataset, a co-authorship network (DBLP), and a Facebook wall-posting network. A key test case was the Enron dataset, where the model tracked the centrality of executives Kenneth Lay and Jeffrey Skilling during the company's collapse.
As shown in Figure 1, the probabilistic MLH method (b) successfully identifies the transition of power, whereas the time-slice method (c) is too erratic and the aggregate method (d) fails to capture Skilling's decline after his resignation.
Discussion and Insights
The probabilistic approach serves as an effective temporal filter, retaining important historical connections while discarding stale ones. It also provides a mathematical justification for the focus on "shortest paths" in network analysis: in an uncertain environment, every additional "hop" increases the likelihood of message loss, making shorter paths the most probable routes for influence.
Furthermore, the direct probabilistic calculations (MLH and Taylor-expansion) achieve results comparable to extensive Monte Carlo sampling but at a significantly lower computational cost. This efficiency allows for more frequent updates and deeper analysis of large-scale dynamic networks.
Conclusion
While the current model assumes edge independence and uses simple exponential decay for probabilities, it provides a powerful framework for analyzing dynamic, uncertain networks. Future work will explore more sophisticated relationship models and optimizations for scaling to massive networks with millions of nodes.
Summary updated