edges_generator

This module uses stochastic block model to generate graphs from tcommlist

It uses networkx.Graph as graph representation.

class BPAM(gamma_in=0.8, gamma_out=0.01, m=5, self_loop=False, seed=None, **kwargs)

Bases: PAM

This class defines a generator of static graphs using Block Preferential Attachment Model (BPAM) [1].

Parameters:

• gamma_in (float) – intra-community interaction index (often called \(\gamma_{kk}\))

• gamma_out – inter-community interaction index (often called \(\gamma_{lk}\))

• m (int) – number of edges created at each step

• self_loop (bool) – enable/disable self loops

• seed (Optional[Any]) –

[1] (1,2)

Wenpin Tang, Xin Guo, and Fengmin Tang. The buckley-osthus model and the block preferential attachment model: statistical analysis and application. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, 9377–9386. PMLR, 13–18 Jul 2020. URL: https://proceedings.mlr.press/v119/tang20b.html.

configure_seed(seed)

Set :attr`seed` and :attr`rng`.

Parameters:

seed (Any) –

Returns:

instance generator

Note

necessary to easily override it while being able to call it

copy()

Return a copy of generator.

Return type:

Self

Returns:

create_graph(commlist)

Create a graph from the provided clusters using Block Preferential Attachment Model (BPAM).

Parameters:

commlist (Tcommlist) –

Returns:

created graph

Return type:

nx.Graph

create_graphs(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

Dict[int, Graph]

Returns:

graphs organized by timesteps

create_graphs_generator(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

GeneratorLen[tuple[int, Graph]]

Returns:

generator of timesteps and corresponding graphs

property rng: Generator

Random number generator of the generator

Return type:

Generator

property seed: SeedSequence

Seed of the generator

Return type:

SeedSequence

spawn(n_children=1)

Spawn a copy of the generated with a child seed.

Return type:

Union[Sequence[Self], Self]

Returns:

new generator

class FastBPAM(gamma_in=0.8, gamma_out=0.01, m=5, self_loop=False, seed=None, **kwargs)

Bases: BPAM

This class defines a generator of static graphs using Block Preferential Attachment Model (BPAM) derived from [2].

Parameters:

• gamma_in (float) – intra-community interaction index (often called \(\gamma_{kk}\))

• gamma_out – inter-community interaction index (often called \(\gamma_{lk}\))

• m (int) – number of edges created at each step

• self_loop (bool) – enable/disable self loops

• seed (Optional[Any]) –

[2] (1,2,3,4)

Roberto Tonelli, Giulio Concas, and Mario Locci. Three efficient algorithms for implementing the preferential attachment mechanism in yule-simon stochastic process. WSEAS Trans. Info. Sci. and App., 7(2):176–185, February 2010. URL: https://dl.acm.org/doi/10.5555/1852489.1852492.

configure_seed(seed)

Set :attr`seed` and :attr`rng`.

Parameters:

seed (Any) –

Returns:

instance generator

Note

necessary to easily override it while being able to call it

copy()

Return a copy of generator.

Return type:

Self

Returns:

create_graph(commlist)

Create a graph from the provided clusters using Block Preferential Attachment Model (BPAM).

Parameters:

commlist (Tcommlist) –

Returns:

created graph

Return type:

nx.Graph

create_graphs(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

Dict[int, Graph]

Returns:

graphs organized by timesteps

create_graphs_generator(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

GeneratorLen[tuple[int, Graph]]

Returns:

generator of timesteps and corresponding graphs

property rng: Generator

Random number generator of the generator

Return type:

Generator

property seed: SeedSequence

Seed of the generator

Return type:

SeedSequence

spawn(n_children=1)

Spawn a copy of the generated with a child seed.

Return type:

Union[Sequence[Self], Self]

Returns:

new generator

class IStaticGraphGenerator(max_iter=10, seed=None)

Bases: IGenerator, ABC

This class defines a common interface for generators of static graphs.

Parameters:

• max_iter (int) –

• seed (Optional[Any]) –

configure_seed(seed)

Set :attr`seed` and :attr`rng`.

Parameters:

seed (Any) –

Returns:

instance generator

Note

necessary to easily override it while being able to call it

copy()

Return a copy of generator.

Return type:

Self

Returns:

abstract create_graph(commlist)

Create a graph using the provided clusters.

Parameters:

commlist (Tcommlist) –

Returns:

created graph

Return type:

nx.Graph

create_graphs(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

Dict[int, Graph]

Returns:

graphs organized by timesteps

create_graphs_generator(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

GeneratorLen[tuple[int, Graph]]

Returns:

generator of timesteps and corresponding graphs

property rng: Generator

Random number generator of the generator

Return type:

Generator

property seed: SeedSequence

Seed of the generator

Return type:

SeedSequence

spawn(n_children=1)

Spawn a copy of the generated with a child seed.

Return type:

Union[Sequence[Self], Self]

Returns:

new generator

class PAM(m=5, self_loop=False, seed=None, **kwargs)

Bases: IStaticGraphGenerator

This class defines a generator of static graphs using Preferential Attachment Model (PAM) [2].

Parameters:

• m (int) – number of edges created at each step

• self_loop (bool) – enable/disable self loops

• seed (Optional[Any]) –

configure_seed(seed)

Set :attr`seed` and :attr`rng`.

Parameters:

seed (Any) –

Returns:

instance generator

Note

necessary to easily override it while being able to call it

copy()

Return a copy of generator.

Return type:

Self

Returns:

create_graph(commlist)

Create a graph from the provided clusters using Preferential Attachment Model (PAM).

Parameters:

commlist (Tcommlist) –

Returns:

created graph

Return type:

nx.Graph

create_graphs(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

Dict[int, Graph]

Returns:

graphs organized by timesteps

create_graphs_generator(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

GeneratorLen[tuple[int, Graph]]

Returns:

generator of timesteps and corresponding graphs

property rng: Generator

Random number generator of the generator

Return type:

Generator

property seed: SeedSequence

Seed of the generator

Return type:

SeedSequence

spawn(n_children=1)

Spawn a copy of the generated with a child seed.

Return type:

Union[Sequence[Self], Self]

Returns:

new generator

class SBM(p_in=0.8, p_out=0.01, max_iter=10, seed=None)

Bases: IStaticGraphGenerator

This class defines a generator of static graphs using Stochastic Block Model (SBM) [3].

Parameters:

• p_in (float) – intra-community edge probability

• p_out (float) – inter-community edge probability

• max_iter (int) –

• seed (Optional[Any]) –

[3] (1,2)

Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: first steps. Social Networks, 5(2):109–137, 1983. doi:10.1016/0378-8733(83)90021-7.

configure_seed(seed)

Set :attr`seed` and :attr`rng`.

Parameters:

seed (Any) –

Returns:

instance generator

Note

necessary to easily override it while being able to call it

copy()

Return a copy of generator.

Return type:

Self

Returns:

create_graph(commlist)

Create a graph from the provided clusters using Stochastic Block Model (SBM).

Parameters:

commlist (Tcommlist) –

Returns:

created graph

Return type:

nx.Graph

create_graphs(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

Dict[int, Graph]

Returns:

graphs organized by timesteps

create_graphs_generator(tcommlist)

Create graphs using the provided tcommlist.

Parameters:

tcommlist (Tcommlist) –

Return type:

GeneratorLen[tuple[int, Graph]]

Returns:

generator of timesteps and corresponding graphs

property rng: Generator

Random number generator of the generator

Return type:

Generator

property seed: SeedSequence

Seed of the generator

Return type:

SeedSequence

spawn(n_children=1)

Spawn a copy of the generated with a child seed.

Return type:

Union[Sequence[Self], Self]

Returns:

new generator

create_graph_bpam(commlist, gamma_in, gamma_out, m, self_loop=False, rng=None)

Returns graph computed from clusters using Block Preferential Attachment Model (BPAM) [1].

A star graph of m nodes is used to initialize it.

Parameters:

• commlist (Tcommlist) –

• gamma_in (float) – intra-community interaction index (often called \(\gamma_{kk}\))

• gamma_out (float) – inter-community interaction index (often called \(\gamma_{lk}\))

• m (int) – number of new edges created per new node

• self_loop (bool) – authorize the choice of self loops (as in the reference article) Warning: the returned graph won’t necessarily be connected!

• rng (Optional[Generator]) – random number generator

Returns:

generated graph

Return type:

nx.Graph

create_graph_fast_bpam(commlist, gamma_in, gamma_out, m, self_loop=False, rng=None)

Returns graph computed from clusters using Block Preferential Attachment Model (BPAM) derived from [2].

Parameters:

• commlist (Tcommlist) –

• gamma_in (float) – intra-community interaction index (often called \(\gamma_{kk}\))

• gamma_out (float) – inter-community interaction index (often called \(\gamma_{lk}\))

• m (int) – number of new edges created per new node

• self_loop (bool) – authorize the choice of self loops Warning: the returned graph won’t necessarily be connected!

• rng (Optional[Generator]) – random number generator

Returns:

generated graph

Return type:

nx.Graph

create_graph_pam(commlist, m, self_loop=False, rng=None)

Returns graph computed from clusters using Preferential Attachment Model (PAM) from [2].

Parameters:

• commlist (Tcommlist) –

• m (int) – number of new edges created per new node

• self_loop (bool) – authorize the choice of self loops Warning: the returned graph won’t necessarily be connected!

• rng (Optional[Generator]) – random number generator

Returns:

generated graph

Return type:

nx.Graph

create_graph_sbm(commlist, p_in, p_out, rng=None)

Returns graph computed from clusters using Stochastic Block Model (SBM) [3].

Parameters:

• commlist (Tcommlist) –

• p_in (float) – intra-community edge density

• p_out (float) – inter-community edge density

• rng (Optional[Generator]) – random number generator

Returns:

Return type:

nx.Graph

main(input_file, out_dir=None, algo=None, p_in=0.8, p_out=0.01, gamma_in=0.8, gamma_out=0.01, m=5, self_loop=False, max_iter=10)

Generate and save graphs as edgelist files from tcommlist file.

Parameters:

• input_file (str) – tcommlist file

• out_dir (str) – output directory to save graphs

• algo (str) – graph generation algorithm to use

• p_in (float) – intra-community edge probability (SBM)

• p_out (float) – inter-community edge probability (SBM)

• gamma_in (float) – intra-community interaction index (often called \(\gamma_{kk}\)) (BPAM)

• gamma_out – inter-community interaction index (often called \(\gamma_{lk}\)) (BPAM)

• m (int) – number of edges created at each step in BPAM

• self_loop (bool) – enable/disable self loops in BPAM

• max_iter – max number of attempts at creating a connected graph for each snapshot in SBM (note: if negative, can loop infinitely until a valid graph is generated)