Designing Efficient and Scalable Substructure Discovery Algorithms for Multilayer Networks
摘要
To model large, complex data sets – with multiple types of entities and relationships – multilayer networks (or MLNs) have been shown to be more effective and computationally efficient as compared to simple and attributed graphs. Analysis algorithms for MLNs are being developed using the decoupling approach and have been shown to be efficient, scalable, and achieve high accuracy. This paper focuses on substructure discovery in homogeneous multilayer networks (or HoMLN, a type of MLN) using a single composition at the end of all iterations for substructure discovery. In this approach, each layer is processed independently for several iterations, and then the results from two or more layers are composed to identify substructures in the entire MLN. The algorithm is designed and implemented, including the composition part, using one of the distributed processing frameworks to ensure scalability. After analyzing the tradeoffs between accuracy and efficiency based on composition frequency, we analyze the speedup and response time of the proposed algorithm for the chosen distributed architecture through extensive experimental analysis on large synthetic and real-world data sets with diverse graph characteristics.