MarkovChain

MarkovChain Class

MarkovChain class, used to perform k-edge on a Graph object.

class kedgeswap.MarkovChain.MarkovChain(graph, N_swap=0, gamma=0, use_jd=False, use_triangles=False, use_assortativity=False, use_mutualdiades=False, verbose=False, keep_record=False, log_dir=None, debug=False)

Bases: object

make swaps

pick_k()

Pick k value using powerlaw distribution. The exponent of the powerlaw can be fixed by the gamma argument.

Returns:

k (int) – number of edges to swap

find_swap(k)

Randomly pick k edges to swap, and randomly pick a permutation When self.force_k == True, permutation is a cyclic permutation, else it is a random permutation, with possible identity for some edges.

Parameters:

k (int) – number of edges to swap

Returns:

• edge_to_swap (list(tuples)) – list of the edges to swap

• permutation (list(tuples)) – list of the edges with which we should swap the edges in edge_to_swap

• _edge_to_swap (list(int)) – indexes in unique_edges of the edges in edge_to_swap

check_swap(edge_to_swap, permutation)

Verify constraints to see if swap can be accepted or not

Parameters:

• edge_to_swap (list(tuples)) – list of the edges to swap

• permutation (list(tuples)) – list of the edges with which we should swap the edges in edge_to_swap

Returns:

swap_accepted (bool) – true if swap can be accepted

check_dyads(edge_to_swap, permutation)

perform_swap(edge_to_swap, permutation, edge_to_swap_idx)

When permutation is accepted, swap the edges in the graph data structure.

Parameters:

• edge_to_swap (list(tuples)) – list of the edges to swap

• permutation (list(tuples)) – list of the edges with which we should swap the edges in edge_to_swap

• edge_to_swap_idx (list(int)) – index of the edges in graph.unique_edges (useful when undirected)

init_assortativity()

Compute Assortativity initial value, using the formula found in “Dutta, Fosdick et Clauset, 2022: Sampling random graphs with specified degree sequences”.

Using the notation deg(u) for the degree of u, and Axy for the adjancency matrix value for nodes x and y, and Sk = sum_x (deg(x) ^ k), we compute the following values:

-S1, S2 and S3, -Sl= sum_xy (Axy * deg(x) * deg(y))

Using these values, the assortativity is computed as :

r = ( S1 * Sl - S2 * S2 ) / ( S1 * S3 - S2 * S2 )

Since Sl is the only value to depend on the presence of each link, we store the denominator to update the assortativity value in O(1) after each swap.

update_assortativity(edge_to_swap, permutation)

Given a K-edge swap, update assortativy value using generalised formual from “Dutta, Fosdick et Clauset, 2022: Sampling random graphs with specified degree sequences”

count_triangles()

Enumerate and store all triangles found in the graph. For undirected graphs:

we store each triangle in a set of tuplet ((u,v,w)) where | u, v and w are the node, with u < v < w, and we store each link | involved in the triangle in edges_in_triangles (pointing to the triangle tuplet) For directed graphs:

we store each triangle thrice in a set of tuplet, with each node as a starting point, | e.g. for triangle (u,v,w) we store {(u,v,w), (v,w,u), (w,u,v)}. We store each link | involved in the triangle in edges_in_triangles (pointing to the triangle tuplet)

update_triangles(edge_to_swap, permutation)

Update the sets of triangles by looking at each edge swap:

• if the initial edge was involved in a triangle, remove triangle from sets

• if the goal edge creates a triangle, add it to the sets

init_joint_degree()

Initialize the joint degree matrix.

joint_degree[i - 1, j - 1] gives the number of links from nodes of degree i to nodes of the degree j. Initialise the joint degree matrix by looping over each node n, then each neighbor nn of n, and incrementing joint_degree[deg(n), deg(nn)] by 1/2. (increment by 1/2 to take into account that each edge is added twice)

update_joint_degree_old(edge_to_swap, permutation)

DEPRECATED - Only used for unit testing ! Given a permutation, compute the changed in the joint degree matrix. Compute the update by copying the joint degree matrix, looping over each edge swap, decrementing the joint degree value for the ‘old’ edges and incrementing the joint degree value for the ‘new’ edges.

Parameters: edge_to_swap : list of the edges to swap permutation : list of the edges with which we should swap the edges in edge_to_swap

Return : updated_joint_degree : np.array, the updated version of the joint degree matrix if the permutation given in input is performed.

update_joint_degree(edge_to_swap, permutation)

Given a permutation, compute the changed in the joint degree matrix. Compute the update by copying the joint degree matrix, looping over each edge swap, decrementing the joint degree value for the ‘old’ edges and incrementing the joint degree value for the ‘new’ edges.

Parameters: edge_to_swap : list of the edges to swap permutation : list of the edges with which we should swap the edges in edge_to_swap

Return : updated_joint_degree : np.array, the updated version of the joint degree matrix if the permutation given in input is performed.

run(N_swap=None)

K-edge swap algorithm. Start by computing assortativity initial value, then perform N_swap, each time checking the constraints and computing metrics.