A MapReduce-Based Approach for Fast Connected Components Detection from Large-Scale Networks.

Area of Science:

• Computer Science
• Data Science
• Network Analysis

Background:

• Classical network processing is infeasible for large, real-world networks due to storage and CPU limitations.
• Real-world network data is often distributed, necessitating distributed processing frameworks like MapReduce.
• Existing MapReduce methods for connected components detection face challenges in minimizing rounds and data transfer.

Purpose of the Study:

• To present an efficient MapReduce-based approach for detecting connected components in large-scale networks.
• To reduce the number of MapReduce rounds and the volume of data processed in subsequent stages.
• To demonstrate the application of the proposed method in contact tracing.

Main Methods:

• Developed an efficient MapReduce algorithm for connected components detection.
• Implemented a strategy to write connected components to the Hadoop Distributed File System (HDFS) upon discovery.
• Reduced data forwarded to subsequent MapReduce rounds by leveraging HDFS storage.

Main Results:

• The proposed method significantly reduces data forwarding compared to existing approaches.
• Empirical evaluations show superior performance and scalability on large network datasets.
• The method proves effective for applications like contact tracing.

Conclusions:

• The novel MapReduce approach offers an efficient and scalable solution for connected components detection in large networks.
• By minimizing data transfer, the method overcomes limitations of traditional distributed processing techniques.
• The approach is well-suited for real-world applications requiring large-scale network analysis.