Top-K Diverse Polarized Communities in Signed Networks

Overview

This repository implements algorithms for the Top-K Diverse Polarized Community (TopK-2PC) problem in signed networks.

A signed network is a graph where each edge carries a sign (+1 for positive/friendly, -1 for negative/antagonistic). A two-polarized community (2PC) is a pair of disjoint node sets (S1, S2) such that nodes within each set are mostly connected by positive edges, while edges between the two sets are mostly negative — a structural signature of polarization.

The TopK-2PC problem asks for K such pairs that are diverse (dissimilar to one another), avoiding the trivial solution of returning the same pair K times.

Primary method: topk_diverse — iteratively solves a diversity-regularized generalized eigenvalue problem on the signed adjacency matrix, penalizing solutions similar to previously found ones via a node-occurrence matrix.

Project Structure

topK-2PC/
├── README.md
├── requirements.txt
├── LICENSE
├── datasets/                          # Real-world signed networks
└── code/
    ├── main.py                        # Entry point
    ├── algorithms/
    │   ├── topk_diverse_eigensign.py  # Primary method (TopK-2PC with diversity)
    │   ├── topk_eigensign.py          # Baselines: topk, topk_random
    │   ├── topk_SCG.py                # Baseline: SCG
    │   ├── topk_spectral.py           # Baselines: SPONGE, BNC
    │   ├── topk_sssnet.py             # Baseline: SSSNET (neural)
    │   ├── topk_timbal.py             # Baseline: TIMBAL (neural)
    │   ├── topk_neural2pc.py          # Baseline: Neural2PC
    │   ├── sgnn_k2.py                 # SignedGCN module (used by Neural2PC)
    │   ├── utility.py                 # Shared utilities
    │   └── subroutines/
    │       └── commons.py             # Objective functions and similarity metrics
    ├── signed_graph/
    │   └── signed_graph.py            # Graph loading and representation
    ├── utilities/
    │   ├── print_console.py
    │   └── time_measure.py
    └── script/
        ├── generate_syndata_topk.py   # Synthetic network generator (MSSBM model)
        ├── compute_f1_synth_topk.py   # F1 evaluation on synthetic data
        ├── process_results_topK.py    # Result aggregation across datasets/runs
        ├── plot_times_topk.py         # Execution time plots
        └── plot_f1_synth.py           # F1 score plots

Installation

pip install -r requirements.txt

Unzip the datasets archive before running any method:

unzip datasets.zip

Neural baselines (topk_sssnet, topk_neural2pc, topk_timbal) require additional packages. Install them separately following each library's own instructions:

pip install torch torch-geometric
pip install torch-geometric-signed-directed   # for topk_sssnet
pip install signet                            # for topk_scg
# topk_timbal requires the RH-TMBS-main/MBS-timbal directory alongside this repo

The spectral baselines (topk, topk_random, topk_diverse, topk_scg, topk_sponge, topk_bnc) do not require any additional packages beyond requirements.txt.

Dataset Format

Each dataset is a plain-text edge list:

# N
u1<TAB>v1<TAB>sign1
u2<TAB>v2<TAB>sign2
...

• First line: # N where N is the number of nodes (IDs are 0-indexed, 0 to N-1)
• Each subsequent line: u<TAB>v<TAB>sign — undirected edge between nodes u and v with sign +1 or -1

The datasets/ directory contains the following real-world networks:

Dataset	Nodes	Domain
highlandtribes	16	Anthropology
cloister	18	Sociology
congress	219	Politics
bitcoin	3783	Finance
wikielections	7118	Wikipedia
twitterreferendum	548	Politics
slashdot	82144	Social
wikiconflict	116836	Wikipedia
epinions	131828	Trust
wikipolitics	138587	Wikipedia
word	8	Linguistics
toy_intro	12	Toy/demo

Generating Synthetic Networks

Synthetic signed networks are generated using the k-pair Modified Signed Stochastic Block Model (k-SSBM) with split-overlap structure.

Model parameters

Parameter	Description
K	Number of planted polarized pairs
N	Total number of nodes
C_size	Per-side community size (set automatically as int(0.2 * N / (2 * K)))
eta	Noise level in [0, 1]: probability that an intra-community edge is negative (or inter-community edge is positive)
rho	Overlap rate in [0, 1]: fraction of nodes shared between consecutive pairs

Running the generator

Edit the parameter grid at the bottom of code/script/generate_syndata_topk.py:

basePath_in = "datasets/"   # output directory (absolute or relative to project root)
Ns     = [1000]
Ks     = [5]
etas   = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6]
rhos   = [0.0, 0.25, 0.5, 0.75]
n_runs = 10

Then run from the project root:

python code/script/generate_syndata_topk.py

Output structure:

datasets/
└── syn_mssbm_K5_rho0.25_eta0.1_N1000_nc20/
    └── sample_0/
        ├── graph.txt           # edge list (same format as real datasets)
        └── ground_truth.json   # planted communities

ground_truth.json fields: K, N, n_c, eta, rho, S1 (list of K lists), S2 (list of K lists).

Running the Methods

All methods are invoked via code/main.py. Run from the project root:

python code/main.py <dataset> <algorithm> [-k K] [-lambd LAMBDA] [-b B] [-p]

Argument	Description	Default
dataset	Dataset name (without .txt)	required
algorithm	Algorithm name (see table below)	required
-k	Number of polarized pairs to find	1
-lambd	Diversity regularization strength (λ)	1.0
-b	Multiplicative factor for topk_random	l1
-p	Print intermediate results	off

Algorithms

Name	Description
topk_diverse	Our method. Iterative generalized eigensign with diversity regularization.
topk	Greedy eigensign without diversity penalty.
topk_random	Randomized eigensign rounding.
topk_scg	Spectral Conflicting Group (SCG) detection baseline.
topk_sponge	SPONGE spectral clustering baseline.
topk_bnc	Balanced Normalized Cut (BNC) baseline.
topk_sssnet	SSSNET baseline.
topk_timbal	TIMBAL baseline.
topk_neural2pc	Neural2PC baseline.

Examples

# Primary method, real dataset, K=5
python code/main.py cloister topk_diverse -k 5 -lambd 1.0

# SCG baseline, K=3
python code/main.py epinions topk_scg -k 3

# Synthetic dataset (after generation)
python code/main.py syn_mssbm_K5_rho0.25_eta0.1_N1000_nc20/sample_0/graph topk_diverse -k 5

# Print intermediate results
python code/main.py bitcoin topk_diverse -k 5 -p

Output

Results are written to output/<dataset>/<algorithm>_results.json. Each entry in the JSON array corresponds to one run:

{
  "solutions": [{"S1": [...], "S2": [...]}, ...],
  "polarity_scores": [float, ...],
  "generalized_polarity_scores": [float, ...],
  "agreement_ratios": [float, ...],
  "jaccard_similarity": [float, ...],
  "cosine_similarity": [float, ...],
  "running_time": float,
  "parameters": {"k": 5, "lambda": 1.0},
  "timestamp": "YYYY-MM-DD HH:MM:SS"
}

• polarity_scores: objective value for each of the K pairs
• generalized_polarity_scores: diversity-aware objective for the full sequence
• agreement_ratios: fraction of edges correctly classified (positive within, negative across)
• jaccard_similarity / cosine_similarity: pairwise similarity between recovered pairs (lower = more diverse); one value per pair (i, j) with i < j

Evaluation on Synthetic Data

After generating synthetic datasets and running the methods, compute F1 scores against planted communities:

# Edit ROOT and result paths at the top of the script first
python code/script/compute_f1_synth_topk.py

Set ROOT in the script to the project root directory and adjust output_folder to where your results are stored.

Processing and Plotting Results

Aggregate results across datasets and methods:

# Edit output_folder, datasets, and methods lists in the script
python code/script/process_results_topK.py

Execution time plots:

python code/script/plot_times_topk.py

F1 score plots (synthetic data):

python code/script/plot_f1_synth.py

Both plotting scripts read from the output/ directory and from the synthetic dataset results. Edit the output_folder, datasets, and methods variables at the top of each script to match your setup.