Network models

Contents

Network models#

The library supports multilayer networks, temporal networks, as well as their composition (i.e., time series of multilayer networks). Below is a list of classes and functions that enable the modelling and manipulation of these complex network structures.

Operations on multilayer networks#

See dedicated multilayer guide for these functions. The library is equipped with two multilayer networks working out-of-the-box: toy_network_piotr and toy_network_cim (Auxiliary functions for operations on MultilayerNetwork).

Class MLNetworkActor#

Implemented in network_diffusion.mln.actor.

class MLNetworkActor(actor_id: str, layers_states: dict[str, str])#

Bases: object

Dataclass that contains actor data in the network.

__init__(actor_id: str, layers_states: dict[str, str]) → None#

Initialise the object.

Parameters:

  • actor_id – id of the actor

  • layers_states – a dictionary keyed by layer names where the actor exists and valued by its state in the given layer

classmethod from_dict(base_dict: dict[str, Any]) → MLNetworkActor#

Create an object from serialised dictionary.

Parameters:

dict – a dictionary with serialised attributes

property layers: tuple[str, ...]#

Retrieve network layers in which an actor exists.

property states: dict[str, str]#

Retrieve an actor’s states where the actor exists.

states_as_compartmental_graph() → tuple[str, ...]#

Return actor states in form accepted by CompartmentalGraph.

Returns:

a tuple in form on (‘process_name.state_name’, …), e.g. (‘awareness.UA’, ‘illness.I’, ‘vaccination.V’)

Class MultilayerNetwork#

Implemented in network_diffusion.mln.mlnetwork.

class MultilayerNetwork(layers: dict[str, Graph])#

Bases: object

A basic container for the multilayer network.

Multilayer network is represented as a dictionary of networkx graphs.

__init__(layers: dict[str, Graph]) → None#

Create an object.

Please note, that all nodes will have initialised “status” attribute to make the network ready for simulations of spreading phenomena.

Parameters:

layers – a layers as networkx graphs.

copy() → MultilayerNetwork#

Create a deep copy of the network.

classmethod from_mpx(file_path: str) → MultilayerNetwork#

Load multilayer network from a mpx file.

mpx is a standard provided by multinet library mainatined by Uppsala University Information Laboratory: uuinfolab Pleas note that multinet is mostly written in C/C++ and it is not possible to control its random numger generator.

Parameters:

file_path – path to the file

classmethod from_nx_layer(network_layer: Graph, layer_names: list[Any]) → MultilayerNetwork#

Create multiplex network from one nx.Graph layer and layers names.

Note that network_layer is replicated through all layers.

Parameters:

  • network_layer – basic layer which is replicated through all ones

  • layer_names – names for layers in multiplex network

classmethod from_nx_layers(network_list: list[Graph], layer_names: list[Any] | None = None) → MultilayerNetwork#

Load multilayer network as list of layers and list of its labels.

Parameters:

  • network_list – list of nx networks

  • layer_names – list of layer names. It can be none, then labels are set automatically

get_actor(actor_id: Any) → MLNetworkActor#

Get actor data basing on its name.

get_actors(shuffle: bool = False) → list[MLNetworkActor]#

Get actors that exist in the network and read their states.

Parameters:

shuffle – a flag that determines whether to shuffle actor list

Returns:

a list with actors that live in the network

get_actors_num() → int#

Get the number of actors in the network.

get_layer_names() → list[str]#

Get names of layers in the network.

Returns:

list of layers’ names

Get links connecting all actors from the network regardless layers.

Returns:

a set with edges between actors

get_nodes_num() → dict[str, int]#

Get the number of nodes in each layer of the network.

is_directed() → bool#

Check whether at least one layer is a DirectedGraph.

is_multiplex() → bool#

Check whether network is multiplex.

save(path: str) → None#

Save the multilayer network as an mpx file.

subgraph(actors: list[MLNetworkActor]) → MultilayerNetwork#

Return a subgraph of the network.

The induced subgraph of the graph contains the nodes in nodes and the edges between those nodes. This is an equivalent of nx.Graph.subgraph.

to_multiplex() → tuple[MultilayerNetwork, dict[str, set[Any]]]#

Convert network to multiplex one by adding missing nodes.

Auxiliary functions for operations on MultilayerNetwork#

Implemented in network_diffusion.mln.

Community based influence maximization algorithm.

cbim_seed_ranking(net: Graph, merging_idx_threshold: float, debug: bool = False, weight_attr: str | None = None) → list[Any]#

Rank all nodes from <net> according to CBIM algorithm.

The routine is a modification of function cbim_seed_selection so that not a given fraction of most influential nodes is returned, but all of them.

Parameters:

  • net – input graph

  • merging_idx_threshold – a threshold above which communities will not be merged anymore during consolidation phase

  • num_seeds – number of seeds to pick, in form of number of nodes

  • debug – if print debug statements, defaults to False

  • weight_attr – which (if any) attribute of edges to use as a weight, defaults to None

Returns:

an ordered ranking of nodes (most influential are at the beggining of the list)

cbim_seed_selection(net: Graph, num_seeds: int, merging_idx_threshold: float, debug: bool = False, weight_attr: str | None = None) → set[Any]#

Select <num_seeds> from <G> according to CBIM algorithm.

The routine was published by Venkatakrishna Rao, C. Ravindranath Chowdary in CBIM: Community-based influence maximization in multilayer networks” (https://doi.org/10.1016/j.ins.2022.07.103) which was published in “Information Sciences”, 2022, Volume 609. This implementation is based on code from here doublejv/CBIM-Implementation, but with several bugs fixed.

Parameters:

  • net – input graph

  • merging_idx_threshold – a threshold above which communities will not be merged anymore during consolidation phase

  • num_seeds – number of seeds to pick, in form of number of nodes

  • debug – if print debug statements, defaults to False

  • weight_attr – which (if any) attribute of edges to use as a weight, defaults to None

Returns:

seed set according to the given budget

detect_communities(net: Graph, merging_idx_threshold: float, debug: bool = False, weight_attr: str | None = None) → list[list[Any]]#

Detect communities according to the CBIM algorithm.

This is an implementation of the Algorithm 2 from “CBIM: Community-based influence maximization in multilayer networks” by Venkatakrishna Rao, C. Ravindranath Chowdary (https://doi.org/10.1016/j.ins.2022.07.103) This implementation is based on doublejv/CBIM-Implementation, but with several bugs fixed.

Parameters:

  • net – input graph

  • merging_idx_threshold – a threshold above which communities will not be merged anymore during consolidation phase

  • debug – if print debug statements, defaults to False

  • weight_attr – which (if any) attribute of edges to use as a weight, defaults to None

Returns:

divison of the nodes into disjoint communities

Script various centrality heuristics defined for multilayer networks.

core_number(net: MultilayerNetwork) → dict[MLNetworkActor, int]#

Return the core number for each actor.

A k-core is a maximal subgraph that contains actors of degree k or more. A core number of a node is the largest value k of a k-core containing that node. Not implemented for graphs with parallel edges or self loops. Overloads networkx.algorithms.core.core_number.

Parameters:

net – multilayer network

Returns:

dictionary keyed by actor to the core number.

degree(net: MultilayerNetwork) → dict[MLNetworkActor, int]#

Return number of links connecting each actor in total on all layers.

k_shell_mln(net: MultilayerNetwork, k: int | None = None, core_number: dict[MLNetworkActor, int] | None = None) → MultilayerNetwork#

Return the k-shell of net with degree computed actorwise.

The k-shell is the subgraph induced by actors with core number k. That is, actors in the k-core that are not in the (k+1)-core. The k-shell is not implemented for graphs with self loops or parallel edges. Overloads networkx.algorithms.core.k_shell.

Parameters:

  • net – A graph or directed graph.

  • k – The order of the shell. If not specified return the outer shell.

  • core_number – Precomputed core numbers keyed by node for the graph net. If not specified, the core numbers will be computed from net.

Returns:

The k-shell subgraph

mean_centrality(net: MultilayerNetwork, centrality_function: Callable) → dict[MLNetworkActor, float]#

Return the mean centrality value for actors.

This function computes a given centraliry (e.g. nx.betweenness_centrality, nx.closeness_centrality’, or `nx.katz_centrality) in every network layer and then return for each actor the average value obtained.

Parameters:

  • net – network to compute centrality for

  • centrality_function – a singlelayer centrality to use

Returns:

dictionary of actors with centraliry values assaigned for.

multiplexing_coefficient(net: MultilayerNetwork) → float#

Compute multiplexing coefficient.

Multiplexing coefficient is defined as proportion of number of nodes common to all layers to number of all unique nodes in entire network

Returns:

(float) multiplexing coefficient

neighbourhood_size(net: MultilayerNetwork, connection_hop: int = 1) → dict[MLNetworkActor, int]#

Return n-hop neighbourhood size for each actor from the network.

Neighbourhood size is the number of actors connected (by n-hop neighbourhood) to the given actor regardless of layers.

number_of_selfloops(net: MultilayerNetwork) → int#

Return the number of selfloop edges in the entire network.

A selfloop edge has the same node at both ends. Overloads networkx.classes. functions.number_of_selfloops.

torch_voterank_actorwise(net: MultilayerNetwork, number_of_actors: int | None = None, device: str | None = None) → list[MLNetworkActor]#

Select a list of influential ACTORS in a graph using VoteRank algorithm.

VoteRank computes a ranking of the actors in a graph based on a voting scheme. With VoteRank, all actors vote for each of its neighbours and the actor with the highest votes is elected iteratively. The voting ability of neighbours of elected actors is decreased in subsequent turns.

Optimised with PyTorch tensors — supports CUDA, MPS (float32), and CPU.

Parameters:

  • net – multilayer network.

  • number_of_actors – number of ranked actors to extract (default all).

  • device – torch device string e.g. “cuda”, “mps”, “cpu”. Auto-detected if not provided (CUDA > MPS > CPU).

Returns:

ordered list of computed seeds, only actors with positive number of votes are returned.

voterank_actorwise(net: MultilayerNetwork, number_of_actors: int | None = None) → list[MLNetworkActor]#

Select a list of influential ACTORS in a graph using VoteRank algorithm.

VoteRank computes a ranking of the actors in a graph based on a voting scheme. With VoteRank, all actors vote for each of its neighbours and the actor with the highest votes is elected iteratively. The voting ability of neighbours of elected actors is decreased in subsequent turns. Overloads networkx.algorithms.core.k_shell.

Parameters:

  • net – multilayer network

  • number_of_actors – number of ranked actors to extract (default all).

Returns:

ordered list of computed seeds, only actors with positive number of votes are returned.

Implementation of actors arnkings basing on Degree Discount algorithm.

degree_discount(net: MultilayerNetwork, k: int) → list[MLNetworkActor]#

Degree Discount Heuristic for MultilayerNetwork.

Routine was invented by W. Chen, Y. Wang, S. Yang in “Efficient Influence Maximization in Social Networks”, (doi.org/10.1145/1557019.1557047). This implementation was slightly modified to be independent on the Independent Cascade Model property - a propagation probability, and we have replaced degree by the algo sensible for multilayer networks. Anyway, the idea stays the same.

Parameters:

  • net – a network to compute seed ranking for

  • k – target size of the seed set

Returns:

a list of actors ordered descending (the higher actor in the list, more central is)

degree_discount_networkx(net: Graph, k: int) → list[Any]#

Degree Discount Heuristic for NetworkX Graph.

Routine was invented by W. Chen, Y. Wang, S. Yang in “Efficient Influence Maximization in Social Networks”, (doi.org/10.1145/1557019.1557047) wchich was published in KDD 09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, p. 199-208. This implementation was slightly modified to be independent on the Independent Cascade Model property - a propagation probability, but the idea stays the same.

Parameters:

  • net – a network to compute seed ranking for

  • k – target size of the seed set

Returns:

a list of nodes ordered descending (the higher node in the list, more central is)

neighbourhood_size_discount(net: MultilayerNetwork, k: int) → list[MLNetworkActor]#

Neighbourhood Size Discount Heuristic for MultilayerNetwork.

Routine was invented by W. Chen, Y. Wang, S. Yang in “Efficient Influence Maximization in Social Networks”, (doi.org/10.1145/1557019.1557047). This implementation was slightly modified to be independent on the Independent Cascade Model property - a propagation probability, and we have replaced degree by neighbourhood size. Anyway, the idea stays the same.

Parameters:

  • net – a network to compute seed ranking for

  • k – target size of the seed set

Returns:

a list of actors ordered descending (the higher actor in the list, more central is)

Script with some functions of NetworkX extended to multilayer networks.

all_neighbours(net: MultilayerNetwork, actor: MLNetworkActor) → Iterator[MLNetworkActor]#

Return all of the neighbours of an actor in the graph.

If the graph is directed returns predecessors as well as successors. Overloads networkx.classes.functions.all_neighbours.

draw_mln(net: MultilayerNetwork, dpi: int = 300) → None#

Draw briefly a given multilayer network.

remove_selfloop_edges(net: MultilayerNetwork) → MultilayerNetwork#

Remove selfloop edges from the network.

squeeze_by_neighbourhood(net: MultilayerNetwork, preserve_mlnetworkactor_objects: bool = True) → Graph#

Squeeze multilayer network to a single layer nx.Graph.

All actors are preserved, links are produced according to naighbourhood between actors regardless layers.

Parameters:

  • net – a multilayer network to be squeezed

  • preserve_mlnetworkactor_objects – a flag indicating how to represent nodes - by MLNetworkActor or primitive types like str, int etc.

Returns:

a networkx.Graph representing net

K++ Shell decomposition functions.

class KPPSNode(node_id: Any, shell: int, reward_points: int)#

Bases: object

K++ Shell auxiliary class for keep state of node.

__init__(node_id: Any, shell: int, reward_points: int) → None#
node_id: Any#
reward_points: int#
shell: int#
to_dict() → dict[str, Any]#

Serialise object into dictionary.

compute_seed_quotas(G: Graph, communities: list[Any], num_seeds: int) → list[int]#

Compute number of seeds to be chosen from communities according to budget.

We would like to select <num_seeds> from the network <G>. This function will compute how many seeds take from each community basing on their sizes compared to size of the <G>. There is a condition: communities should be separable, i.e. each node must be in only one community.

get_toy_network_kppshell() → MultilayerNetwork#

Get a toy network that was used by the authors of K++ Shell method.

The paper is here: https://doi.org/10.1016/j.comnet.2023.109916

kppshell_decomposition(G: Graph) → list[list[dict[str, Any]]]#

Decompose network according to K++ shell routine.

The routine was published by Venkatakrishna Rao, C. Ravindranath Chowdary in “K++ Shell: Influence maximization in multilayer networks using community detection” (https://doi.org/10.1016/j.comnet.2023.109916) which was published in “Computer Networks”, 2023, Volume 234. The method was optimised by the authors of Network Diffusion and deprived of ambiguities. We also made an assumption that during communities detection every node can be assigned only to one community. Another assumption was that we accept communities that consist of at least one node. These conditions were not considered in the original paper.

Parameters:

G – a network to be decomposed

Returns:

a list of communities detected in the network in which all nodes are represented as dict with thei IDs, shells they are assigned to and reward points their gained during decomposition.

kppshell_seed_ranking(G: Graph) → list[Any]#

Rank all nodes from <G> according to K++ Shell decomposition.

The routine is a modification of function kppshell_seed_selection so that not a given fraction of most influential nodes is returned but all of them.

Parameters:

G – a network to create ranking of all nodes from

Returns:

an ordered ranking of nodes (most influential are at the beggining of the list)

kppshell_seed_selection(G: Graph, num_seeds: int) → set[Any]#

Select <num_seeds> from <G> according to K++ Shell decomposition.

The routine was published by Venkatakrishna Rao, C. Ravindranath Chowdary in “K++ Shell: Influence maximization in multilayer networks using community detection” (https://doi.org/10.1016/j.comnet.2023.109916) which was published in “Computer Networks”, 2023, Volume 234. The method was optimised by the authors of Network Diffusion and deprived of ambiguities.

Parameters:

  • G – a network to pick seeds from

  • num_seeds – number of seeds to pick, in form of number of nodes

Returns:

a set of nodes picked

Class MultilayerNetworkTorch#

Implemented in network_diffusion.mln.mlnetwork_torch.

class MultilayerNetworkTorch(adjacency_tensor: Tensor, layers_order: list[str], actors_map: bidict, nodes_mask: Tensor)#

Bases: object

Representation of MultilayerNetwork in a tensor notation.

Note, that in order to provide consistency between channels of an adjacency matrix, the network is converted to multiplex with nodes added artifically marked in the property nodes_mask. Features of edges and actors are NOT preserved.

Parameters:

  • adjacency_tensor – adjacency matrix as a sparse tensor shaped as [nb. layers x nb. actors x nb. actors]

  • layers_order – names of layers in an order that is preserved in adjacency_tensor

  • actors_map – map of actor names Any -> int between the original network and its sparse representation

  • nodes_mask – mask of nodes added while making the network multiplex ordered in the same way as the nodes in adjacency_tensor

  • device – a device where tensor-members of the object are stored in

__init__(adjacency_tensor: Tensor, layers_order: list[str], actors_map: bidict, nodes_mask: Tensor) → None#
actors_map: bidict#
adjacency_tensor: Tensor#
copy() → MultilayerNetworkTorch#

Crete a copy of the object.

property device: str#

Get a device where the object’s data is stored.

classmethod from_mln(net: MultilayerNetwork, device: str = 'cpu') → MultilayerNetworkTorch#

Represent net in a tensor notation.

layers_order: list[str]#
nodes_mask: Tensor#

Operations on temporal networks#

A TemporalNetwork is an ordered sequence of MultilayerNetwork objects. In a base scenario, one can obtain a classic temporal network by having a chain of one-layered MultilayerNetwork.

Please bear in mind that to perform simulations on TemporalNetwork objects, they must have the same set of actors on each snapshot!

The library is equipped with an exemplar temporal-multilayer network: l2_course_net (:ref:aux-tpn-label).

Class TemporalNetwork#

Implemented in network_diffusion.tpn.

class TemporalNetwork(snaps: list[MultilayerNetwork])#

Bases: object

A container for temporal network.

__init__(snaps: list[MultilayerNetwork]) → None#

Create a temporal network object.

Parameters:

snaps – snapshots of the temporal network.

classmethod from_cogsnet(forgetting_type: str, snapshot_interval: int, edge_lifetime: int, mu: float, theta: float, units: int, path_events: str, delimiter: str) → TemporalNetwork#

Load events from a csv file and create CogSNet.

Note, the csv file should be in the form of: SRC DST TIME. The timestamps TIME should be in ascending order. The timestamps are expected to be provided in seconds.

Parameters:

  • forgetting_type (str) – The forgetting function used to decrease the weight of edges over time. Allowed values are ‘exponential’, ‘power’, or ‘linear’.

  • snapshot_interval (int) – The interval for taking snapshots (0 or larger) expressed in units param (seconds, minutes, hours). A value of 0 means taking a snapshot after each event.

  • edge_lifetime (int) – The lifetime of an edge after which the edge will disappear if no new event occurs (greater than 0).

  • mu (float) – The value of increasing the weight of an edge for each new event (greater than 0 and less than or equal to 1).

  • theta (float) – The cutoff point (between 0 and mu). If the weight falls below theta, the edge will disappear.

  • units (int) – The time units (1 for seconds, 60 for minutes, or 3600 for hours). For the power forgetting function, this parameter also determines the minimum interval between events to prevent them from being skipped when calculating the weight.

  • path_events (str) – The path to the CSV file with events.

  • delimiter (str) – The delimiter for the CSV file (allowed values are ‘,’, ‘;’, or ‘\t’).

classmethod from_nx_layers(network_list: list[Graph], snap_ids: list[Any] | None = None) → TemporalNetwork#

Load a temporal network from a list of networks and their snapshot ids.

Parameters:

  • network_list – a list of nx networks

  • snap_ids – list of snapshot ids. It can be none, then ids are set automatically, if not, then snapshots will be sorted according to snap_ids list

classmethod from_txt(file_path: str, time_window: int, directed: bool = True) → TemporalNetwork#

Load a temporal network from a txt file.

Note, the txt file should be in the form of: SRC DST UNIXTS. The timestamps UNIXTS should be in ascending order. The timestamps are expected to be provided in seconds.

Parameters:

  • file_path – path to the file

  • time_window – the time window size for each snapshot

  • directed – indicate if the graph is directed

get_actors(shuffle: bool = False) → list[MLNetworkActor]#

Get actors that from the first snapshot of network.

Parameters:

shuffle – a flag that determines whether to shuffle actor list

get_actors_from_snap(snapshot_id: int, shuffle: bool = False) → list[MLNetworkActor]#

Get actors that exist in the network at given snapshot.

Parameters:

  • snapshot_id – snapshot for which to take actors, starts from 0

  • shuffle – a flag that determines whether to shuffle actor list

get_actors_num() → int#

Get the number of actors in the network.

Functions for the auxiliary operations on temporal networks.

read_tpn(file_path: str, time_window: int, directed: bool = True) → dict[int, Graph | DiGraph]#

Read temporal network from a text file for the dict of NetworkX networks.

Parameters:

file_path – path to file

Returns:

a dictionary keyed by snapshot ID and valued by NetworkX Graph

Contents