TCNR: Rethinking Node Centrality for High-Dynamics Mobile Social Networks

TL;DR

Calculating node importance in Mobile Social Networks (MSNs) using static snapshots is fundamentally flawed because it ignores the trajectory of topology changes. This paper introduces TCNR (Time-ordered Cumulative Neighboring Relationship), a metric that redefines centrality by considering both social contact regularity and the temporal sequence of interactions. By applying an exponential weighting model, the authors prove that when you meet someone matters just as much as how often you meet them.

Background: The Static Graph Fallacy

In MSNs, where devices use a "store-carry-and-forward" scheme, identifying the most influential "hubs" is vital for data dissemination. However, traditional centrality measures (Degree, Betweenness) treat the network as a frozen slice of time. The authors demonstrate that a node appearing central in a static aggregate might actually be a bottleneck or even disconnected in a real, time-ordered sequence.

The Core Innovation: Capturing Social "Neighboring Relationship"

The authors argue that the "separating time" between nodes—which accounts for both contact frequency and duration—is the best proxy for social closeness.

1. The CNR Metric

They define Neighboring Relationship (NR) between nodes $i$ and $j$ by normalizing the average separating time (${\alpha }_{ij}$) and its variance (${\beta }_{ij}$):

• ASep: Normalized average separating time.
• VSep: Normalized variance (regularity).
• CNR: The sum of these relationships across the network, including multi-hop paths.

2. Time-Ordered Aggregation Model

A dynamic network is reduced to a series of snapshots $(G_1,G_2,\dots ,G_n)$. The innovation lies in how these snapshots are summed. The authors propose the Exponential Time-ordered Aggregation Method:

The intuition is that early contact is more valuable for propagation than late contact. Therefore, weights $(heta)$ decrease exponentially from the start of the time interval to the end.

Experimental Proof: Trace-Driven Validation

The model was tested against two famous datasets: MIT Reality (long-term stable social patterns) and Infocom 06 (short-term conference interaction).

Performance vs. Other Aggregation Methods

The results confirm that the "Exponential" weighting (Exp.) correlates much more strongly with actual message propagation delay $D(i)$ than Average (Ave.) or Static (Sta.) methods.

TCNR vs. Existing SOTA Temporal Metrics

When compared to Temporal Degree (TDeg) and Temporal Betweenness (TBet), TCNR showed superior stability and accuracy, especially in the MIT Reality trace.

Critical Insight & Takeaway

The paper’s most profound insight is the temporal decay of influence. In a forwarding scenario, a node that is active early in a window has a higher "utility" because it maximizes the remaining time for the message to travel.

However, there is a catch: in highly chaotic environments like the Infocom conference (where contacts are often singular and non-repeating), TCNR’s advantage narrows. This suggests that the model is most potent in networks with an underlying social structure (workplaces, campuses, fixed commutes).

Conclusion

TCNR moves beyond the "what" and "how many" of network centrality into the "when." For developers of DTN (Delay-Tolerant Network) routing protocols, moving to an exponential time-weighted centrality model could yield significant gains in delivery ratios and latency reduction.