It is believed that the minimum connected dominating set problem cannot be solved in polynomial time. To the best of my knowledge, there is no source code available for approximation algorithms. Therefore, I decide to implement one proposed by M. Rai in 2009.

1. MCDS-NON-DISTRIBUTED

1.1 Descriptions

The algorithm I implemented is proposed by M. Rai in 2009.

RAI, M., GARG, N., VERMA, S., et al. A new heuristic approach for minimum connected dominating set in adhoc wireless networks. In : Advance Computing Conference, 2009. IACC 2009. IEEE International. IEEE, 2009. p. 284-289.

The main idea of MCDS-NON-DISTRIBUTED is to form a connected dominating set by transversing all nodes (either breadth first search or depth first search) and continuously removing the node v if G(V-v) is still connected.

• Transverse nodes, beginning with the node u with the maximum degree. Therefore, we have CDS = {u}, Q = {N(u)} (enqueue u‘s neighbors in descending order by their degree)
• Pop a node from the queue Q, add v to CDS if G(V-v) is not yet connected otherwise remove it
• Loop until the queue Q is empty, then we get a connected dominating set for G

1.2 Implementation

The key source code is as follows. Click GitHub, complex networks, dominating sets to access the full source code.

# Step 1: initialization
# take the node with maximum degree as the starting node
starting_node = max(G2.degree().items(), key=operator.itemgetter(1))[0] 
fixed_nodes = {starting_node}

# Enqueue the neighbor nodes of starting node to Q in descending order by their degree
neighbor_nodes = G2.neighbors(starting_node)
neighbor_nodes_sorted = OrderedDict(sorted(G2.degree(neighbor_nodes).items(), key=operator.itemgetter(1), reverse=True)).keys()

priority_queue = deque(neighbor_nodes_sorted) # a priority queue is maintained centrally to decide whether an element would be a part of CDS.

inserted_set = set(neighbor_nodes_sorted + [starting_node])

# Step 2: calculate the cds
while priority_queue:
    u = priority_queue.pop()

    # check if the graph after removing u is still connected
    rest_graph = copy.deepcopy(G2)
    rest_graph.remove_node(u)

    if nx.is_connected(rest_graph):
        G2.remove_node(u)
    else: # is not connected 
        fixed_nodes.add(u)

        # add neighbors of u to the priority queue, which never are inserted into Q
        inserted_neighbors = set(G2.neighbors(u)) - inserted_set
        inserted_neighbors_sorted = OrderedDict(sorted(G2.degree(inserted_neighbors).items(),
                                                        key=operator.itemgetter(1), reverse=True)).keys()

        priority_queue.extend(inserted_neighbors_sorted)
        inserted_set.update(inserted_neighbors_sorted)

return fixed_nodes

1.3 An example

Take Florentine families graph as an example, as shown below, the nodes in red is a connected dominating set.

References:
[1]Wikipedia: Connected dominating set
[2]RAI, M., GARG, N., VERMA, S., et al. A new heuristic approach for minimum connected dominating set in adhoc wireless networks. In : Advance Computing Conference, 2009. IACC 2009. IEEE International. IEEE, 2009. p. 284-289.

赞赏

微信赞赏支付宝赞赏