A Unified Core Structure in Multiplex Networks: From Finding the Densest Subgraph to Modeling User Engagement
Open Access
- 24 August 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1028-1039
Abstract
In many complex systems, the interactions between objects span multiple aspects. Multiplex networks are accurate paradigms to model such systems, where each edge is associated with a type. A key graph mining primitive is extracting dense subgraphs, and this has led to interesting notions such as k-cores, known as building blocks of complex networks. Despite recent attempts to extend the notion of core to multiplex networks, existing studies suffer from a subset of the following limitations: They (1) force all nodes to exhibit their high degree in the same set of relation types while in multiplex networks some connection types can be noisy for some nodes, (2) either require high computational cost or miss the complex information of multiplex networks, and (3) assume the same importance for all relation types. We introduce Score, a novel and unifying family of dense structures in multiplex networks that uses a function S(.) to summarize the degree vector of each node. We then discuss how one can choose a proper S(.) from the data. To demonstrate the usefulness of Scores, we focus on finding the densest subgraph as well as modeling user engagement in multiplex networks. We present a new density measure in multiplex networks and discuss its advantages over existing density measures. We show that the problem of finding the densest subgraph in multiplex networks is NP-hard and design an efficient approximation algorithm based on Scores. Finally, we present a new mathematical model of user engagement in the presence of different relation types. Our experiments shows the efficiency and effectiveness of our algorithms and supports the proposed mathematical model of user engagement.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Discovering Cohesive Temporal Subgraphs with Temporal Density Aware ExplorationJournal of Computer Science and Technology, 2022
- Efficient Adoption Maximization in Multi-layer Social Networks2019
- Core decomposition in large temporal graphs2015
- Finding Dense Subgraphs in Relational Graphs2015
- Structural reducibility of multilayer networksNature Communications, 2015
- percolation on multiplex networksPhysical Review E, 2014
- Temporal networksPhysics Reports, 2012
- Fast algorithms for determining (generalized) core groups in social networksAdvances in Data Analysis and Classification, 2010
- A General Tractable Density Concept for GraphsMathematics in Computer Science, 2008
- Online summarization of dynamic time series dataThe VLDB Journal, 2005