NSDlib

NSDlib (Network source detection library) is a comprehensive library designed for detecting sources of propagation in networks. This library offers a variety of algorithms that help researchers and developers analyze and identify the origins of information (epidemic etc.) spread within networks.

Overview

NSDLib is a complex library designed for easy integration into existing projects. It aims to be a comprehensive repository of source detection methods, outbreak detection techniques, and propagation graph reconstruction tools. Researchers worldwide are encouraged to contribute and utilize this library, facilitating the development of new techniques to combat misinformation and improve propagation analysis. Each year, new techniques are introduced through scientific papers, often with only pseudo-code descriptions, making it difficult for researchers to evaluate and compare them with existing methods. NSDlib tries to bridge this gap and enhance researchers to put their implementations here.

Code structure

All custom implementations are provided under nsdlib/algorithms package. Each method is implemented in a separate file, named after the method itself and in appropriate package according to its intended purpose e.g. reconstruction algorithm should be placed in reconstruction package. . Correspondingly, each file contains a function, named identically to the file, which does appropriate logic. Ultimately, every custom implementation is made available through the nsdlib/algorithms package.

Implemented features:

Node evaluation algorithms

• algebraic_centrality
• average_distance_centrality
• barycenter_centrality
• betweenness_centrality
• bottle_neck_centrality
• centroid_centrality
• closeness_centrality
• cluster_rank_centrality
• communicability_betweenness_centrality
• coreness_centrality
• current_flow_betweenness_centrality
• current_flow_closeness_centrality
• decay_centrality
• degree_centrality
• diffusion_degree_centrality
• dynamic_age
• eccentricity_centrality
• eigenvector_centrality
• entropy_centrality
• geodestic_k_path_centrality
• group_betweenness_centrality
• group_closeness_centrality
• group_degree_centrality
• harmonic_centrality
• heatmap_centrality
• hubbell_centrality
• jordan_center
• katz_centrality
• laplacian_centrality
• leverage_centrality
• lin_centrality
• load_centrality
• mnc_centrality
• net_sleuth
• pagerank_centrality
• pdi_centrality
• percolation_centrality
• radiality_centrality
• rumor_centrality
• second_order_centrality
• semi_local_centrality
• subgraph_centrality
• topological_centrality
• trophic_levels_centrality
• algebraic_centrality
• average_distance_centrality
• barycenter_centrality
• betweenness_centrality
• bottle_neck_centrality
• centroid_centrality
• closeness_centrality
• cluster_rank_centrality
• communicability_betweenness_centrality
• coreness_centrality
• current_flow_betweenness_centrality
• current_flow_closeness_centrality
• decay_centrality
• degree_centrality
• diffusion_degree_centrality
• eccentricity_centrality
• eigenvector_centrality
• entropy_centrality
• geodestic_k_path_centrality
• group_betweenness_centrality
• group_closeness_centrality
• group_degree_centrality
• harmonic_centrality
• heatmap_centrality
• hubbell_centrality
• katz_centrality
• laplacian_centrality
• leverage_centrality
• lin_centrality
• load_centrality
• mnc_centrality
• pagerank_centrality
• pdi_centrality
• percolation_centrality
• radiality_centrality
• rumor_centrality
• second_order_centrality
• semi_local_centrality
• subgraph_centrality
• topological_centrality
• trophic_levels_centrality

Outbreak detection algorithms

• CPM_Bipartite
• agdl
• angel
• aslpaw
• async_fluid
• bayan
• belief
• bimlpa
• coach
• condor
• conga
• congo
• core_expansion
• cpm
• dcs
• demon
• der
• dpclus
• ebgc
• ego_networks
• eigenvector
• em
• endntm
• eva
• frc_fgsn
• ga
• gdmp2
• girvan_newman
• graph_entropy
• greedy_modularity
• head_tail
• hierarchical_link_community
• ilouvain
• infomap
• infomap_bipartite
• ipca
• kclique
• kcut
• label_propagation
• lais2
• leiden
• lemon
• lfm
• louvain
• lpam
• lpanni
• lswl
• lswl_plus
• markov_clustering
• mcode
• mod_m
• mod_r
• multicom
• node_perception
• overlapping_seed_set_expansion
• paris
• percomvc
• principled_clustering
• pycombo
• r_spectral_clustering
• rb_pots
• rber_pots
• ricci_community
• sbm_dl
• sbm_dl_nested
• scan
• siblinarity_antichain
• significance_communities
• slpa
• spectral
• spinglass
• surprise_communities
• threshold_clustering
• tiles
• umstmo
• wCommunity
• walkscan
• walktrap

Graph reconstruction algorithms

• SbRP

Ensemble methods

This package provides implementation for easily combining multiple source detection methods into one ensemble method. Use 'EnsembleSourceDetector' with config objects as arguments to create an ensemble method.

How to use

Library can be installed using pip:

pip install nsdlib

Code usage

Provided algorithms can be executed in the following ways:

• by utilizing 'SourceDetector' class and configuring it with 'SourceDetectionConfig' object. This approach allows for seamless source detection and result evaluation.

import networkx as nx

from nsdlib.common.models import SourceDetectionConfig
from nsdlib.source_detection import SourceDetector
from nsdlib.taxonomies import NodeEvaluationAlgorithm


G = nx.karate_club_graph()

config = SourceDetectionConfig(
    node_evaluation_algorithm=NodeEvaluationAlgorithm.NETSLEUTH,
)

source_detector = SourceDetector(config)

result, evaluation = source_detector.detect_sources_and_evaluate(G=G,
                                        IG=G, real_sources=[0,33])
print(evaluation)

For performing ensemble source detection, use 'EnsembleSourceDetector' class and configure it with 'EnsembleSourceDetectionConfig' object. This approach allows for seamless source detection and result evaluation.

import networkx as nx

from nsdlib.common.models import SourceDetectionConfig, \
    EnsembleSourceDetectionConfig
from nsdlib.source_detection import SourceDetector, EnsembleSourceDetector
from nsdlib.taxonomies import NodeEvaluationAlgorithm, EnsembleVotingType

G = nx.karate_club_graph()

config_netsleuth = SourceDetectionConfig(
    node_evaluation_algorithm=NodeEvaluationAlgorithm.NETSLEUTH,
)

config_degree = SourceDetectionConfig(
    node_evaluation_algorithm=NodeEvaluationAlgorithm.CENTRALITY_DEGREE,
)

ensemble_config = EnsembleSourceDetectionConfig(
    detection_configs=[config_netsleuth, config_degree],
    voting_type=EnsembleVotingType.HARD,
    classifier_weights=[0.5, 0.5],
)

source_detector = EnsembleSourceDetector(ensemble_config)

result, evaluation = source_detector.detect_sources_and_evaluate(G=G,
                                        IG=G, real_sources=[0,33])
print(evaluation)

• by importing and using specific method, each method has appropriate prefix to understand what is the purpose of it:

import networkx as nx

import nsdlib as nsd

G = nx.karate_club_graph()
IG = G.copy()
IG.remove_nodes_from([10,15,20,33])
real_sources = [0,8]

EIG = nsd.reconstruction_sbrp(G, IG)

outbreaks = nsd.outbreaks_leiden(EIG)

detected_sources = []
for outbreak in outbreaks.communities:
    outbreak_G = G.subgraph(outbreak)
    nodes_evaluation = nsd.evaluation_jordan_center(outbreak_G)
    outbreak_detected_source = max(nodes_evaluation, key=nodes_evaluation.get)
    print(f"Outbreak: {outbreak}, Detected Source: {outbreak_detected_source}")
    detected_sources.append(outbreak_detected_source)

evaluation = nsd.compute_source_detection_evaluation(
    G=EIG,
    real_sources=real_sources,
    detected_sources=detected_sources,
)
print(evaluation)

This method allows you to directly specify the process of source detection, making it easy to do any modifications to standardlogic.

• by using appropriate enum and method for computing desired method:

import networkx as nx

import nsdlib as nsd
from nsdlib import PropagationReconstructionAlgorithm, NodeEvaluationAlgorithm, OutbreaksDetectionAlgorithm

G = nx.karate_club_graph()
IG = G.copy()
IG.remove_nodes_from([10,15,20,33])
real_sources = [0,8]

EIG = nsd.reconstruct_propagation(G, IG, PropagationReconstructionAlgorithm.SBRP)

outbreaks = nsd.identify_outbreaks(EIG, OutbreaksDetectionAlgorithm.LEIDEN)
outbreaks_G = nsd.create_subgraphs_based_on_outbreaks(EIG, outbreaks)
detected_sources = []
for outbreak in outbreaks_G:
    nodes_evaluation = nsd.evaluate_nodes(outbreak, NodeEvaluationAlgorithm.CENTRALITY_AVERAGE_DISTANCE)
    outbreak_detected_source = max(nodes_evaluation, key=nodes_evaluation.get)
    print(f"Outbreak: {outbreak}, Detected Source: {outbreak_detected_source}")
    detected_sources.append(outbreak_detected_source)

evaluation = nsd.compute_source_detection_evaluation(
    G=EIG,
    real_sources=real_sources,
    detected_sources=detected_sources,
)
print(evaluation)

This approach is more flexible and allows for the computation of multiple techniques at once or when iterating over multiple methods making it easy to perform analysis of selected set of techniques.

For more examples and details, please refer to the official documentation.

Contributing

For contributing, refer to its CONTRIBUTING.md file. We are a welcoming community... just follow the Code of Conduct.

Maintainers

Project maintainers are:

• Damian Frąszczak
• Edyta Frąszczak