Centrality-Based Connected Dominating Sets for Complex Network Graphs

Centrality-Based Connected Dominating Sets for Complex Network Graphs

Natarajan Meghanathan
DOI: 10.4018/ijitn.2014040101
(Individual Articles)
No Current Special Offers


The author proposes the use of centrality-metrics to determine connected dominating sets (CDS) for complex network graphs. The author hypothesizes that nodes that are highly ranked by any of these four well-known centrality metrics (such as the degree centrality, eigenvector centrality, betweeness centrality and closeness centrality) are likely to be located in the core of the network and could be good candidates to be part of the CDS of the network. Moreover, the author aims for a minimum-sized CDS (fewer number of nodes forming the CDS and the core edges connecting the CDS nodes) while using these centrality metrics. The author discusses our approach/algorithm to determine each of these four centrality metrics and run them on six real-world network graphs (ranging from 34 to 332 nodes) representing various domains. The author observes the betweeness centrality-based CDS to be of the smallest size in five of the six networks and the closeness centrality-based CDS to be of the smallest size in the smallest of the six networks and incur the largest size for the remaining networks.
Article Preview


Network Science has been an actively researched area for analysis and visualization of characteristics of large complex real-world networks. Several metrics (a.k.a. measures) have been used for network analysis. Of these, centrality of the nodes constituting the network (a measure of the importance of the nodes with respect to the rest of the nodes) is one of the key metrics. The centrality-based ranking of nodes in real-world networks is purely a link-statistic based approach and does not depend on any offline information such as reputation of the particular entity representing the node, etc (Newman, 2010). The widely-used centrality metrics are: Degree, Betweeness, Eigenvector and Closeness, all of which are studied in this paper.

We model large real-world network as a graph of vertices and edges (vertices represent the nodes - entities like players, countries, airports, books, etc constituting the real-world network, and edges represent the interactions between these entities in the form of competitions played against, airline connections, books related to a particular domain, etc). The currently available application software (e.g., (Gephi, 2014 & Pajek, 2014) as well as literature for network analysis and visualization focus on several graph theoretic properties like diameter, clustering coefficient, path length, components, communities, etc. To the best of our knowledge, we could not find any work on determining minimum connected dominating sets (CDS) of these real-world networks. A CDS (Cormen et al., 2009) of a graph is a subset of the vertices (and the edges connecting these vertices) such that every vertex in the graph is either in the CDS or is connected to a node in the CDS (in the latter case, the node is said to be covered by a node in the CDS).

A CDS forms the connected backbone of a network graph and could be used as the underlying communication topology for broadcasting throughout the network with the minimum number of forward transmissions (Meghanathan, 2012a). Only the nodes constituting the CDS need to forward a message (to the other nodes constituting the CDS) and the rest of the nodes in the network could be mere receivers. Accordingly, the primary objective of CDS-related research has been to find CDS of smaller size. Unfortunately, the problem of finding a minimum connected dominating set (CDS with the fewest number of constituent nodes) in both weighted and unit-weight graphs (undirected or directed) is a NP-hard problem (Cormen et al., 2009). Several heuristics (Gu et al, 2012; Meghanathan, 2012a, etc) have been proposed to find approximations to minimum-sized CDS. A common theme among all of these heuristics is to use a metric (like node degree) as the determining factor to include a node as part of the CDS. CDS construction starts with the node having the maximum value for the underlying metric and the nodes connected to this starting node are considered candidate nodes for inclusion to the CDS (as long as these nodes bring in at least one node that is yet to be covered). Among such candidate nodes, the node that covers the largest number of uncovered nodes is included to the CDS; this procedure is continued until all the nodes in the network graph are covered by at least one node in the CDS.

In this paper, we study the use of centrality metrics to determine CDS on large complex network graphs. Our objective is to identify one or more centrality metrics that could be used to determine CDS of smaller size in real-world networks. In this direction, we implement algorithms to determine some of the commonly used centrality metrics (Degree centrality, Eigenvector centrality, Betweeness centrality and Closeness centrality) and run them on six real-world network graphs of different sizes (ranging from 34 nodes to 332 nodes). Results obtained indicate the Betweeness centrality to be the most suited metric to determine smaller sized CDS (with respect to both the number of nodes constituting the CDS as well as the number of edges between these CDS nodes) for large complex network graphs. The Betweeness centrality scheme ranks a node based on the number of shortest paths that the node is part of between any source-destination pair and the number of such source-destination pairs on whose shortest paths the node is located.

Complete Article List

Search this Journal:
Volume 16: 1 Issue (2024)
Volume 15: 1 Issue (2023)
Volume 14: 1 Issue (2022)
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing