提出可扩展的同质多层网络子结构发现算法，提升复杂网络分析效率。
Scalable Substructure Discovery Algorithm For Homogeneous Multilayer Networks
- 采用分层独立处理+结果融合的解耦方法，提升计算效率。
- 在大规模合成与真实数据集上实现显著加速，响应时间大幅降低。
- 适合需要高效分析多层复杂网络的应用场景，如社交网络、生物网络。
图挖掘通过分析现实世界中的图数据，识别核心子结构（连通子图），广泛应用于各类图模型问题。子结构发现旨在从大规模数据集中识别有意义的模式、结构或组件，包括频繁模式、图谱等。为建模包含多种实体和关系的复杂数据，多层网络（MLNs）相比传统图更有效。基于解耦方法的MLN分析算法已被证明兼具高效性与准确性。本文聚焦于同质多层网络（一种MLN）中的子结构发现，提出一种新颖的解耦方法：各层独立处理后，融合两层及以上结果以识别全网络子结构。算法设计并实现，结合分布式框架（Map/Reduce）以保证可扩展性。通过大量合成与真实数据集实验，验证了算法正确性，并分析了速度提升与响应时间表现，覆盖多样图特征。
原文摘要 · Abstract (English)
Graph mining analyzes real-world graphs to find core substructures (connected subgraphs) in applications modeled as graphs. Substructure discovery is a process that involves identifying meaningful patterns, structures, or components within a large data set. These substructures can be of various types, such as frequent patterns, motifs, or other relevant features within the data. To model complex data sets -- with multiple types of entities and relationships -- multilayer networks (or MLNs) have been shown to be more effective as compared to simple and attributed graphs. Analysis algorithms on MLNs using the decoupling approach have been shown to be both efficient and accurate. Hence, this paper focuses on substructure discovery in homogeneous multilayer networks (one type of MLN) using a novel decoupling-based approach. In this approach, each layer is processed independently, 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 (the Map/Reduce paradigm) to provide scalability. After establishing the correctness, we analyze the speedup and response time of the proposed algorithm and approach through extensive experimental analysis on large synthetic and real-world data sets with diverse graph characteristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。