Systems, Man, and Cybernetics

 

Home

• [P1045] Classes of Optimal Network Topologies Under Multiple Effciency and Robustness Constraints
  Author(s): Sanket Patil, Srinath Srinivasa, Venkat Venkatasubramanian
  
  

  Abstract
  We address the problem of designing optimal network topologies under arbitrary optimality requirements. Using three critical system parameters, efficiency, robustness and cost, we evolve optimal topologies under different environmental conditions. Two prominent classes of topologies emerge as optimal: (1) Star-like (or scale-free) topologies, with high efficiency, high resilience to random failures and low cost, and (2) "Circular Skip Lists" (CSL), with high robustness to random failures as well as targeted attacks, and high efficiency at moderate cost. We observe a sharp transition from star-like topologies to CSL as emphasis on robustness increases or cost restrictions become less severe. We analyze CSLs further to observe that they show several structural motifs that are optimal with respect to a variety of metrics.

  
   

Full Text (PDF)