def qubo_matrix_community_sparse()

in src/qubo_community.py [0:0]

• 13 lines of code
• 10 McCabe index (conditional complexity)

def qubo_matrix_community_sparse(nx_G, k, alpha=5):
    """
    Create a sparse matrix as a QUBO matrix for a graph nx_G with k-community detection

    :param nx_G: networkX graph
    :param k: int, the number of communities to detect for the graph nx_G
    :param alpha: float, the penalty coefficient for the constraint term in the QBUO matrix
    :return: scipy coo sparse matrix, the QUBO matrix to minimize for a graph nx_G with k-community detection
    """
    
    # get the number of nodes for a networkx graph
    num_nodes = nx_G.number_of_nodes()

    # create the modularity matrix in coo sparse format
    modu_mx_sparse = modularity_mx(nx_G)

    # define the coefficient value for the QUBO constraint term that a node can only be in one community
    gamma_v = alpha / num_nodes
    
    # create sparse diagonal matrix for the linear constraint term in the QUBO matrix
    gamma_mx = sp.eye(num_nodes) * gamma_v
    
    # create a block diagonal matrix for k-commnuity problem where k > 2
    # this block diagonal matrix is for the linear constraint term in the QUBO matrix 
    gamma_blockmatrix_sparse = sp.block_diag([gamma_mx] * k)

    # create a k x k sparse block matrix with each block being a diagonal matrix
    # this block matrix is for the quadratic constraint term in the QUBO matrix
    constraint_mx = [[gamma_mx] * k] * k
    constraint_blockmatrix_sparse = sp.bmat(constraint_mx)
    
    # create a sparse block diagonal matrix with the diagonal value equal to the modularity matrix
    # this is the modularity matrix for k communities in QUBO format
    modu_mx_sparse_k = [modu_mx_sparse] * k
    modu_block_sparse = sp.block_diag(modu_mx_sparse_k)

    # create a QUBO sparse matrix (for minimization) by combinding the modularity matrix and the constraint
    # term matrix for a k-community problem
    q_blockmatrix_sparse = -1 * modu_block_sparse + constraint_blockmatrix_sparse - 2 * gamma_blockmatrix_sparse
    q_blockmatrix_sparse = sp.coo_matrix(q_blockmatrix_sparse)

    return q_blockmatrix_sparse