Qatalyst
Get Started

Community Detection

Community detection finds the communities among a set of vertices in a graph that maximizes a specific modularity function. While similar to partitioning and clustering, community detection is different in that it tries to maximize modularity as the figure of merit (compared with minimizing the number of inter-partition cut edges and making the partitions the same size, for partitioning). Modularity is defined as the fraction of edges that fall within the assigned communities minus the expected fraction if edges were distributed randomly [GN].
Note that community detection does not simply look for equally sized partitions, whereas graph partitioning does. Hence the figure below and the similar figure on the partition page are slightly different.
A depiction of the Zachary Karate Club social interactions is portrayed in [GN] and a depiction of communities detected by the community detection algorithm is described in [NUMM].

Running a Community Detection job

Download a local copy of a Jupyter notebook with a community detection example

Input data

To upload an undirected graph, we encode it in a NetworkX graph
1
Let G = nx.random_geometric_graph(n=3, radius=0.4, dim=2, seed=518) .
Alternatively, we encode it in a square symmetric matrix, in which we encode it in a sparse matrix format as shown below. We use Numpy array notation.
1
Let A = np.array([[0, -1.5, 0.5], [-1.5, 0, 0], [0.5, 0, 0]]) ,

API format

We encode the above in a sparse dictionary format for the upload step to the API:
1234567891011121314151617181920212223242526272829303132333435363738
graph_data = { 
 "directed": false, 
 "multigraph": false, 
 "graph": {},
 "nodes": [{"id": 0}, {"id": 1}, {"id": 2}]
  "links": [
    {
      "source": 0,
      "target": 1,
      "weight": -1.5
    },
    {
      "source": 0,
      "target": 2,
      "weight": 0.5
    },
    {
      "source": 1,
      "target": 0,
      "weight": -1.5
    },
    {
      "source": 2,
      "target": 0,
      "weight": 0.5
    }
  ],
  "params" : 
    {
       "alpha": 3, 
       "num_communities": 4, 
       "sampler_type": "eqc1", 
       "n_samples": 10
    },
  "file_name": "graph.json", # can be any short string
  "num_variables": 3, # number of rows
  "file_type": "graph" # defines the data type, 'graph' in this case
}

Uploading

First, import the necessary packages:
123
import json
from qci_client import QciClient
qci = QciClient()
Now we can upload the various files using the client. Suppose we store the data in a variable data. Then we call upload_file to push the data to the server.
12
response_json = qci.upload_file(graph_data)
file_id = response_json["file_id"]
We can extract the file_id for later use. Triggering a job to run requires the file_id to tell the backend which data to use. We cover this step in the Running tab.

Contents