Graph-theoretic abstractions are extensively used to analyze
massive data sets. Temporal data streams from socio-economic
interactions, social networking web sites, communication
traffic, and scientific computing can be intuitively
modeled as graphs. We present the first study of novel high-performance
combinatorial techniques for analyzing large-scale
information networks, encapsulating dynamic interaction
data in the order of billions of entities. We present new
data structures to represent dynamic interaction networks,
and discuss algorithms for processing parallel insertions and
deletions of edges in small-world networks. With these new
approaches, we achieve an average performance rate of 25
million structural updates per second and a parallel speedup
of nearly 28 on a 64-way Sun UltraSPARC T2 multicore
processor, for insertions and deletions to a small-world
network of 33.5 million vertices and 268 million edges.
We also design parallel implementations of fundamental
dynamic graph kernels related to connectivity and centrality
queries. Our implementations are freely distributed as part
of the open-source SNAP (Small-world Network Analysis
and Partitioning) complex network analysis framework.
