Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
Open Access
- 27 February 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 886-894
Abstract
Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, where we have a number of edge sets called layers, which encode different types of connections and/or time-dependent connections over the same set of vertices. Among many network analysis techniques, dense subgraph discovery, aiming to find a dense component in a network, is an essential primitive with a variety of applications in diverse domains. In this paper, we introduce a novel optimization model for dense subgraph discovery in multilayer networks. Our model aims to find a stochastic solution, i.e., a probability distribution over the family of vertex subsets, rather than a single vertex subset, whereas it can also be used for obtaining a single vertex subset. For our model, we design an LP-based polynomial-time exact algorithm. Moreover, to handle large-scale networks, we also devise a simple, scalable preprocessing algorithm, which often reduces the size of the input networks significantly and results in a substantial speed-up. Computational experiments demonstrate the validity of our model and the effectiveness of our algorithms.Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (JP17K12646, JP19K20218, JP20K19739, JP21K17708, JP21H03397)
- Japan Science and Technology Agency (JPMJPR2122)
This publication has 23 references indexed in Scilit:
- Spreading Processes in Multilayer NetworksIEEE Transactions on Network Science and Engineering, 2015
- Ranking in interconnected multilayer networks reveals versatile nodesNature Communications, 2015
- Experimental manipulation of avian social structure reveals segregation is carried over across contextsProceedings Of The Royal Society B-Biological Sciences, 2015
- The structure and dynamics of multilayer networksPhysics Reports, 2014
- Multilayer networksJournal of Complex Networks, 2014
- Mathematical Formulation of Multilayer NetworksPhysical Review X, 2013
- Functional and Effective Connectivity: A ReviewBrain Connectivity, 2011
- A Survey of Algorithms for Dense Subgraph Discovery2010
- Greedy Approximation Algorithms for Finding Dense Components in a Graph2000
- Generating Sparse 2-SpannersJournal of Algorithms, 1994