Cost-Effective Community-Hierarchy-Based Mutual Voting Approach for Influence Maximization in Complex Networks

• URL: http://arxiv.org/abs/2409.14034v1
• Date: Sat, 21 Sep 2024 06:32:28 GMT
• Title: Cost-Effective Community-Hierarchy-Based Mutual Voting Approach for Influence Maximization in Complex Networks
• Authors: Yi Liu, Xiaoan Tang, Witold Pedrycz, Qiang Zhang,
• Abstract summary: Real-world usually have high requirements on the balance between time and accuracy of influential nodes identification. This article proposes a novel approach called Cost-Effective Community-Hierarchy-Based Mutual Voting for influence in complex networks. The proposed approach outperforms 16 state-of-the-art techniques on the balance between time complexity and accuracy of influential nodes identification.
• Score: 54.366995393644586
• License:
• Abstract: Various types of promising techniques have come into being for influence maximization whose aim is to identify influential nodes in complex networks. In essence, real-world applications usually have high requirements on the balance between time complexity and accuracy of influential nodes identification. To address the challenges of imperfect node influence measurement and inefficient seed nodes selection mechanism in such class of foregoing techniques, this article proposes a novel approach called Cost-Effective Community-Hierarchy-Based Mutual Voting for influence maximization in complex networks. First, we develop a method for measuring the importance of different nodes in networks based on an original concept of Dual-Scale Community-Hierarchy Information that synthesizes both hierarchy structural information and community structural information of nodes. The community structural information contained in the nodes is measured by a new notion of Hierarchical-Community Entropy. Second, we develop a method named Cost-Effective Mutual-Influence-based Voting for seed nodes selection. Hereinto, a low-computational-cost mutual voting mechanism and an updating strategy called Lazy Score Updating Strategy are newly constructed for optimizing the selecting of seed nodes. Third, we develop a balance index to evaluate the performance of different methods in striking the tradeoff between time complexity and the accuracy of influential nodes identification. Finally, we demonstrate the approach performance over ten public datasets. The extensive experiments show that the proposed approach outperforms 16 state-of-the-art techniques on the balance between time complexity and accuracy of influential nodes identification. Compared with the method with the second highest value of the balance index, our approach can be improved by at most 9.29%.

Related papers

• LayerPlexRank: Exploring Node Centrality and Layer Influence through Algebraic Connectivity in Multiplex Networks [4.130399938456945]
  This paper introduces LayerPlexRank, an algorithm that simultaneously assesses node centrality and layer influence in multiplex networks. We substantiate the utility of LayerPlexRank with theoretical analyses and empirical validations on varied real-world datasets.
  arXiv  Detail & Related papers  (2024-05-09T06:52:24Z)
• Effective Reinforcement Learning Based on Structural Information Principles [19.82391136775341]
  We propose a novel and general Structural Information principles-based framework for effective Decision-Making, namely SIDM. SIDM can be flexibly incorporated into various single-agent and multi-agent RL algorithms, enhancing their performance.
  arXiv  Detail & Related papers  (2024-04-15T13:02:00Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  We study a semi-supervised community detection problem in which the objective is to estimate the community label of a new node. We propose an algorithm that computes a structural similarity metric' between the new node and each of the $K$ communities. Our findings highlight, to the best of our knowledge, the first semi-supervised community detection algorithm that offers theoretical guarantees.
  arXiv  Detail & Related papers  (2023-06-01T19:02:50Z)
• Robust Knowledge Adaptation for Dynamic Graph Neural Networks [61.8505228728726]
  We propose Ada-DyGNN: a robust knowledge Adaptation framework via reinforcement learning for Dynamic Graph Neural Networks. Our approach constitutes the first attempt to explore robust knowledge adaptation via reinforcement learning. Experiments on three benchmark datasets demonstrate that Ada-DyGNN achieves the state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-07-22T02:06:53Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN) In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries. By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Joint Learning of Hierarchical Community Structure and Node Representations: An Unsupervised Approach [15.379817564640712]
  We present Mazi, an algorithm that jointly learns the hierarchical community structure and the node representations of the graph in an unsupervised fashion. We evaluate our method on a variety of synthetic and real-world graphs and demonstrate that Mazi outperforms other hierarchical and non-hierarchical methods.
  arXiv  Detail & Related papers  (2022-01-22T15:48:10Z)
• IM-META: Influence Maximization Using Node Metadata in Networks With Unknown Topology [13.704584231053675]
  We propose a solution to influence (IM) in networks with unknown topology by retrieving information from queries and node metadata. In IM-META, we develop an effective method that iteratively performs three steps: 1) we learn the relationship between collected metadata and edges via a neural Siamese network, 2) we select a number of inferred confident edges to construct a reinforced graph, and 3) we identify the next node to query by maximizing the inferred influence spread.
  arXiv  Detail & Related papers  (2021-06-05T16:11:02Z)
• Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks [68.9026534589483]
  RioGNN is a novel Reinforced, recursive and flexible neighborhood selection guided multi-relational Graph Neural Network architecture. RioGNN can learn more discriminative node embedding with enhanced explainability due to the recognition of individual importance of each relation.
  arXiv  Detail & Related papers  (2021-04-16T04:30:06Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.