Hide and Seek: Outwitting Community Detection Algorithms

• URL: http://arxiv.org/abs/2102.10759v1
• Date: Mon, 22 Feb 2021 03:50:44 GMT
• Title: Hide and Seek: Outwitting Community Detection Algorithms
• Authors: Shravika Mittal, Debarka Sengupta, Tanmoy Chakraborty
• Abstract summary: Community affiliation plays an important role in determining a node's contextual position in a network. This study focuses on hiding such sensitive communities so that the community affiliation of the targeted nodes can be concealed. We introduce NEURAL, a novel method that greedily optimize a node-centric objective function to determine the rewiring strategy.
• Score: 17.144388833011536
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community affiliation of a node plays an important role in determining its contextual position in the network, which may raise privacy concerns when a sensitive node wants to hide its identity in a network. Oftentimes, a target community seeks to protect itself from adversaries so that its constituent members remain hidden inside the network. The current study focuses on hiding such sensitive communities so that the community affiliation of the targeted nodes can be concealed. This leads to the problem of community deception which investigates the avenues of minimally rewiring nodes in a network so that a given target community maximally hides from a community detection algorithm. We formalize the problem of community deception and introduce NEURAL, a novel method that greedily optimizes a node-centric objective function to determine the rewiring strategy. Theoretical settings pose a restriction on the number of strategies that can be employed to optimize the objective function, which in turn reduces the overhead of choosing the best strategy from multiple options. We also show that our objective function is submodular and monotone. When tested on both synthetic and 7 real-world networks, NEURAL is able to deceive 6 widely used community detection algorithms. We benchmark its performance with respect to 4 state-of-the-art methods on 4 evaluation metrics. Additionally, our qualitative analysis of 3 other attributed real-world networks reveals that NEURAL, quite strikingly, captures important meta-information about edges that otherwise could not be inferred by observing only their topological structures.

Related papers

• Contrastive Deep Nonnegative Matrix Factorization for Community Detection [29.143384185705617]
  We propose a new community detection algorithm, named Contrastive Deep Nonnegative Matrix Factorization (CDNMF) Inspired by contrastive learning, our algorithm creatively constructs network topology and node attributes as two contrasting views. We conduct experiments on three public real graph datasets and the proposed model has achieved better results than state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-11-04T09:50:37Z)
• Evading Community Detection via Counterfactual Neighborhood Search [10.990525728657747]
  Community detection is useful for social media platforms to discover tightly connected groups of users who share common interests. Some users may wish to preserve their anonymity and opt out of community detection for various reasons, such as affiliation with political or religious organizations, without leaving the platform. In this study, we address the challenge of community membership hiding, which involves strategically altering the structural properties of a network graph to prevent one or more nodes from being identified by a given community detection algorithm.
  arXiv  Detail & Related papers  (2023-10-13T07:30:50Z)
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection [0.0]
  Community detection aims to partition a network into clusters of nodes to summarize its large-scale structure. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model. Other methods are descriptive, dividing a network according to an objective motivated by a particular application. We present a solution that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model.
  arXiv  Detail & Related papers  (2022-10-17T15:38:41Z)
• Improving Fraud detection via Hierarchical Attention-based Graph Neural Network [6.7713383844867385]
  Graph Neural Network (HA-GNN) for fraud detection incorporates weighted adjacency matrices across different relations against camouflage. We generate node embeddings by aggregating information from local/long-range structures and original node features. Experiments on three real-world datasets demonstrate the effectiveness of our model over the state-of-the-arts.
  arXiv  Detail & Related papers  (2022-02-12T16:27:16Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Uncovering the Local Hidden Community Structure in Social Networks [20.467702194064525]
  We propose a new method that detects and boosts each layer iteratively on a subgraph sampled from the original network. We theoretically show that our method can avoid some situations that a broken community and the local community are regarded as one community in the subgraph.
  arXiv  Detail & Related papers  (2021-12-08T04:07:19Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• 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)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  We propose a graph meta-learning framework -- Graph Prototypical Networks (GPN) GPN is able to perform textitmeta-learning on an attributed network and derive a highly generalizable model for handling the target classification task.
  arXiv  Detail & Related papers  (2020-06-23T04:13:23Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)
• Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing [81.71105567425275]
  We develop the first certified robustness guarantee of community detection against adversarial structural perturbation. We theoretically show that the smoothed community detection method provably groups a given arbitrary set of nodes into the same community. We also empirically evaluate our method on multiple real-world graphs with ground truth communities.
  arXiv  Detail & Related papers  (2020-02-09T18:39:39Z)

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.