Journal
COMPUTER COMMUNICATIONS
Volume 33, Issue 17, Pages 2093-2104Publisher
ELSEVIER
DOI: 10.1016/j.comcom.2010.07.013
Keywords
Interconnection networks; Network modeling; Cayley graph; Borel Cayley graph; Graph theory
Categories
Funding
- National Science Foundation [CNS 0829656, IIP 0917956]
Ask authors/readers for more resources
A graph theoretic approach is proposed to formulate communication graphs that enable ultrafast information distribution. In our earlier work, we reported that Borel Cayley graph (BCG) is a promising candidate as a logical topology for fast information distribution. However, the practical applications of BCG have been challenging because of its inflexible sizes. In this paper, we propose a simple but effective graph resizing algorithm that removes nodes from an oversized BCG to achieve a desired network size The proposed resizing algorithm consists of two parts; a random pruning algorithm that identifies nodes to be removed uniformly at random; and a novel cut-through rewiring (CUR) algorithm that rewires the remaining nodes. The proposed resizing algorithm preserves the superior properties of the original BCGs, including a small diameter, a short average path length, a large algebraic connectivity, and ultrafast information distribution performance. Furthermore, analytical formulae were derived to compute the graph disconnection probability of the BCGs after resizing Analytical results showed that the resized graphs are almost surely connected even after 80 similar to 90% size reduction, depending on the original BCG size (C) 2010 Elsevier B V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available