# Utility¶

## Transformations¶

graspy.utils.pass_to_ranks(graph, method='simple-nonzero')[source]

Rescales edge weights of an adjacency matrix based on their relative rank in the graph.

Parameters: graph: Adjacency matrix method: {'simple-nonzero' (default), 'simple-all', 'zero-boost'} string, optional 'simple-nonzero' assigns ranks to all non-zero edges, settling ties using the average. Ranks are then scaled by $$\frac{rank(\text{non-zero edges})}{\text{total non-zero edges} + 1}$$ 'simple-all' assigns ranks to all non-zero edges, settling ties using the average. Ranks are then scaled by $$\frac{rank(\text{non-zero edges})}{n^2 + 1}$$ where n is the number of nodes 'zero-boost' preserves the edge weight for all 0s, but ranks the other edges as if the ranks of all 0 edges has been assigned. If there are 10 0-valued edges, the lowest non-zero edge gets weight 11 / (number of possible edges). Ties settled by the average of the weight that those edges would have received. Number of possible edges is determined by the type of graph (loopless or looped, directed or undirected). graph: numpy.ndarray, shape(n_vertices, n_vertices) Adjacency matrix of graph after being passed to ranks
graspy.utils.to_laplace(graph, form='DAD', regularizer=None)[source]

A function to convert graph adjacency matrix to graph Laplacian.

Currently supports I-DAD, DAD, and R-DAD Laplacians, where D is the diagonal matrix of degrees of each node raised to the -1/2 power, I is the identity matrix, and A is the adjacency matrix.

R-DAD is regularized Laplacian: where $$D_t = D + regularizer*I$$.

Parameters: graph: object Either array-like, (n_vertices, n_vertices) numpy array, or an object of type networkx.Graph. form: {'I-DAD' (default), 'DAD', 'R-DAD'}, string, optional 'I-DAD' Computes $$L = I - D*A*D$$ 'DAD' Computes $$L = D*A*D$$ 'R-DAD' Computes $$L = D_t*A*D_t$$ where $$D_t = D + regularizer*I$$ regularizer: int, float or None, optional (default=None) Constant to be added to the diagonal of degree matrix. If None, average node degree is added. If int or float, must be >= 0. Only used when form == 'R-DAD'. L: numpy.ndarray 2D (n_vertices, n_vertices) array representing graph Laplacian of specified form

References

 [1] Qin, Tai, and Karl Rohe. "Regularized spectral clustering under the degree-corrected stochastic blockmodel." In Advances in Neural Information Processing Systems, pp. 3120-3128. 2013

Examples

>>> a = np.array([
...    [0, 1, 1],
...    [1, 0, 0],
...    [1, 0, 0]])
>>> to_laplace(a, "DAD")
array([[0.        , 0.70710678, 0.70710678],
[0.70710678, 0.        , 0.        ],
[0.70710678, 0.        , 0.        ]])

graspy.utils.augment_diagonal(graph, weight=1)[source]

Replaces the diagonal of adjacency matrix with $$\frac{degree}{nverts - 1}$$ for the degree associated with each node.

For directed graphs, the degree used is the out degree (number) of edges leaving the vertex. Ignores self-loops when calculating degree

Parameters: graph: nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph, np.ndarray Input graph in any of the above specified formats. If np.ndarray, interpreted as an $$n \times n$$ adjacency matrix graph: np.array Adjacency matrix with average degrees added to the diagonal.

Examples

>>> a = np.array([
...    [0, 1, 1],
...    [1, 0, 0],
...    [1, 0, 0]])
>>> augment_diagonal(a)
array([[1. , 1. , 1. ],
[1. , 0.5, 0. ],
[1. , 0. , 0.5]])

graspy.utils.symmetrize(graph, method='avg')[source]

A function for forcing symmetry upon a graph.

Parameters: graph: object Either array-like, (n_vertices, n_vertices) numpy matrix, or an object of type networkx.Graph. method: {'avg' (default), 'triu', 'tril',}, optional An option indicating which half of the edges to retain when symmetrizing. 'avg' Retain the average weight between the upper and lower right triangle, of the adjacency matrix. 'triu' Retain the upper right triangle. 'tril' Retain the lower left triangle. graph: array-like, shape (n_vertices, n_vertices) the graph with asymmetries removed.

Examples

>>> a = np.array([
...    [0, 1, 1],
...    [0, 0, 1],
...    [0, 0, 1]])
>>> symmetrize(a, method="triu")
array([[0, 1, 1],
[1, 0, 1],
[1, 1, 1]])

graspy.utils.remove_loops(graph)[source]

A function to remove loops from a graph.

Parameters: graph: object Either array-like, (n_vertices, n_vertices) numpy matrix, or an object of type networkx.Graph. graph: array-like, shape(n_vertices, n_vertices) the graph with self-loops (edges between the same node) removed.

## Connected Components¶

graspy.utils.is_fully_connected(graph)[source]

Checks whether the input graph is fully connected in the undirected case or weakly connected in the directed case.

Connected means one can get from any vertex u to vertex v by traversing the graph. For a directed graph, weakly connected means that the graph is connected after it is converted to an unweighted graph (ignore the direction of each edge)

Parameters: graph: nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph, np.ndarray Input graph in any of the above specified formats. If np.ndarray, interpreted as an $$n \times n$$ adjacency matrix boolean: True if the entire input graph is connected

References

Examples

>>> a = np.array([
...    [0, 1, 0],
...    [1, 0, 0],
...    [0, 0, 0]])
>>> is_fully_connected(a)
False

graspy.utils.get_lcc(graph, return_inds=False)[source]

Finds the largest connected component for the input graph.

The largest connected component is the fully connected subgraph which has the most nodes.

Parameters: graph: nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph, np.ndarray Input graph in any of the above specified formats. If np.ndarray, interpreted as an $$n \times n$$ adjacency matrix return_inds: boolean, default: False Whether to return a np.ndarray containing the indices in the original adjacency matrix that were kept and are now in the returned graph. Ignored when input is networkx object graph: nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph, np.ndarray New graph of the largest connected component of the input parameter. inds: (optional) Indices from the original adjacency matrix that were kept after taking the largest connected component
graspy.utils.get_multigraph_union_lcc(graphs, return_inds=False)[source]

Finds the union of all multiple graphs, then compute the largest connected component.

Parameters: graphs: list or np.ndarray List of array-like, (n_vertices, n_vertices), or list of np.ndarray nx.Graph, nx.DiGraph, nx.MultiDiGraph, nx.MultiGraph. return_inds: boolean, default: False Whether to return a np.ndarray containing the indices in the original adjacency matrix that were kept and are now in the returned graph. Ignored when input is networkx object out : list or np.ndarray If input was a list

## IO¶

graspy.utils.import_graph(graph, copy=True)[source]

A function for reading a graph and returning a shared data type.

Parameters: graph: object Either array-like, shape (n_vertices, n_vertices) numpy array, or an object of type networkx.Graph. copy: bool, (default=True) Whether to return a copied version of array. If False and input is np.array, the output returns the original input. out: array-like, shape (n_vertices, n_vertices) A graph.

See also

networkx.Graph, numpy.array
graspy.utils.import_edgelist(path, extension='edgelist', delimiter=None, nodetype=<class 'int'>, return_vertices=False)[source]

Function for reading a single or multiple edgelists. When importing multiple edgelists, the union of vertices from all graphs is computed so that each output graph have matched vertex set. The order of nodes are sorted by node values.

Parameters: path : str, Path object, or iterable If path is a directory, then the importing order will be sorted in alphabetical order. extension : str, optional If path is a directory, then the function will convert all files with matching extension. delimiter : str or None, default=None, optional Delimiter of edgelist. If None, the delimiter is whitespace. nodetype : int (default), float, str, Python type, optional Convert node data from strings to specified type. return_vertices : bool, default=False, optional Returns the union of all ind out : list of array-like, or array-like, shape (n_vertices, n_vertices) If path is a directory, a list of arrays is returned. If path is a file, an array is returned. vertices : array-like, shape (n_vertices, ) If return_vertices == True, then returns an array of all vertices that were included in the output graphs.