Community detection using fast low-cardinality semidefinite programming

A system for performing community detection, comprising:

• one or more computing devices, programmed to:
• receive data descriptive of a set of nodes of a network, the data including a set of nodes representing entities of a system and edges representing connections between the entities of the system;
• perform a modularity maximization to assign each node of the set of nodes to one or more communities to generate multiple-cardinality embeddings;
• round the multiple-cardinality embeddings to unit cardinality to recover a community assignment with maximum modularity;
• refine and aggregate the community assignment to create an aggregate network defining a set of connected communities of the network;
• and
• operate on the network in accordance with the community assignment.

A non-transitory computer-readable medium comprising instructions for performing community detection, that, when executed by one or more computing devices, cause the one or more computing devices to perform operations including to:

• receive data descriptive of a set of nodes of a network, the data including a set of nodes represent entities of a system and edges representing connections between the entities of the system;
• perform a modularity maximization to assign each node of the set of nodes to one or more communities to generate multiple-cardinality embeddings;
• round the multiple-cardinality embeddings to unit cardinality to recover a community assignment with maximum modularity;
• refine and aggregate the community assignment to create an aggregate network defining a set of connected communities of the network;
• and
• operate on the network in accordance with the community assignment,
• wherein the data descriptive of the set of nodes of the network describes of one or more of a physical, chemical, mechanical, economic, social, epidemiological, biological, neuronal, or computational system, and the set of connected communities indicate a community structure of the system.