I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks

Area of Science:

• Graph theory and network analysis
• Data mining and machine learning
• Computational social science

Background:

• Temporal networks capture dynamic relationships, crucial for understanding real-world phenomena.
• Bursting cohesive subgraphs (BCS) identify rapidly intensifying events but existing methods lack timeliness.
• Early detection of burstiness is vital for applications like emergency response and epidemic tracking.

Purpose of the Study:

• To propose an early bursting cohesive subgraph (EBCS) model for timely identification of burstiness in temporal networks.
• To develop efficient algorithms for finding EBCS, addressing limitations of existing BCS methods.
• To enable analysis of massive temporal networks with limited memory resources.

Main Methods:

• Constructing a time weight graph (TWG) integrating topological and temporal information.
• Developing global search (GS-EBCS) and local search (LS-EBCS) algorithms for EBCS identification.
• Designing I/O-efficient algorithms (I/O-GS, I/O-LS) for handling large-scale temporal networks under a semi-external model.

Main Results:

• The proposed EBCS model effectively identifies bursty events earlier than traditional BCS methods.
• GS-EBCS and LS-EBCS demonstrate efficiency in finding EBCS.
• I/O-LS significantly reduces memory usage (e.g., 6.5 MB vs. 308.7 MB) for large datasets while maintaining comparable performance to LS-EBCS.

Conclusions:

• The EBCS model provides a timely and effective approach to analyzing burstiness in temporal networks.
• The developed algorithms, particularly I/O-LS, offer efficient solutions for analyzing massive temporal networks.
• This research advances the understanding and detection of critical events in dynamic network data.