graphy.partitions - Module to search over partitions

Module implementing tools to work with partitions of sets as well as perform heuristic optimization over set partitions.

graphy.partitions.to_str(membership)

Convert membership array to pretty string.

Example:

>>> from graphy import partitions
>>> print(partitions.to_str([0,0,0,1,1,1]))
[0 0 0 1 1 1]

Parameters:

membershipnp.array or list

Membership array to convert

Returns:

str

Pretty string

graphy.partitions.to_alphanum_str(membership)

Convert membership array to short string.

Example:

>>> from graphy import partitions
>>> print(partitions.to_alphanum_str([0,0,0,1,1,1,2,3,4,20,20,20]))
[000111234KKK]

Parameters:

membershipnp.array or list

Membership array to convert

Returns:

str

Short pretty string

graphy.partitions.get_minsize_assignment(N, min_comm_size)

Create membership vector where each community contains at least as a certain number of nodes.

Parameters:

Nint

Desired length of membership vector

min_comm_sizeint

Minimum number of nodes each community should have.

Returns:

np.array

Membership vector

graphy.partitions.renumber_membership(membership)

Renumber membership vector so that community numbers begin with 0 and increase consecutively.

Example:

>>> from graphy import partitions
>>> print(partitions.renumber_membership([10,10,10,31,31,31,32,33,4,20]))
[3 3 3 5 5 5 0 1 2 4]

Parameters:

membershipnp.array

Membership array to renumber

Returns:

np.array

Renumber membershp array

graphy.partitions.remap2match(partition1, partition2)

Renumber membership assignments so that community identities have maximal overlap with another membership assignment.

For example:

>>> from graphy import partitions
>>> print(remap2match([3,3,1,1,0],[2,2,3,3,3]))
[2 2 3 3 4]

Parameters:

partition1np.array or list

Membership assignment to remap

partition2np.array or list

Membership assignment to match

Returns:

np.array

Remapped assignment

graphy.partitions.greedy_search(qualityfunc, N, initial_membership=None, num_runs=1, debug_level=0)

Find optimal decomposition using a greedy search.

Parameters:

qualityfuncfunction

Function which returns the quality measure to be maximized.

Nint

Number of nodes to partition.

initial_membershipnp.array, optional

Initial membership assignment. If None specified, each component is assigned to separate subsystem.

num_runsint, optional

Number of runs to try, can improve quality of decompositions. Default is 1.

debug_levelint, optional

Amount of debugging information to display, from 0 (no debugging information) to 3 (maximal debugging information)

Returns:

np.array

Optimal membership array

float

Q value corresponding to optimal membership