Graphs Generation for Network Computing Simulations

Overview

• GGen randomly generates a graph with a specific type and connectivity ratio.

function [kappa_G,P,per_t,fig,connectivity]=GGen2(L,per,name,show_graph,quiet,arg_opt1)

• Required parameters:
  • L: number of nodes
  • per: expected connectivity ratio
  • name: the type of the graph, can be Random, Line, Star, Complete, Cycle, Regular, Bipartite, Biclique, k-NNG (nearest neighbor graph), RGG (random geometric graph), Hierarchical (temporarily not available in the current version), 2D grid, and 3D grid
  • show_graph: plot the graph or not, true/false
  • quiet: silent mode or not, true/false
  • arg_opt1: optional parameters reserved for some specific types of graphs
    • (1) Regular graph: arg_opt1 is the degree of the nodes
    • (2) Bipartite graph: the number of nodes in one part
    • (3) k-NNG graph: k, the number neighbors
    • (4) RGG: the Radius of connectivity
    • (5) 2D Grid: a vector containing the length and the width of the 2D Grid
    • (6) 3D Grid: a vector containing the length, the width, and the height of the 3D Grid
• Return values:
  • kappa_G: the condition number of the graph
  • P: adjacency matrix of the generated graph
  • per_t: the actual connectivity ratio
  • fig: the figure handle of the plotted graph, exists only when show_graph=true
  • connectivity: the algebraic connectivity of the generated graph
• Examples:
  • [kappa_G,P,per_t,fig]=GGen2(10,0.5,'random') randomly generates a connected 10-nodes graph with connectivity ratio around 0.5.
  • [kappa_G,P,per_t,fig]=GGen2(0,0.5,'3D Grid',true,true,[3,5,10]) randomly generates a 3D Grid with specified size [3,5,10].
  • [kappa_G,P,per_t,fig]=GGen2(60,0,'regular',false,true,3) randomly generates a connected regular graph with 60 nodes and degree 3.
• References:
  • [1] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, “On the Linear Convergence of the ADMM in Decentralized Consensus Optimization,” IEEE Transactions on Signal Processing, vol. 62, no. 7, pp. 1750-1761, 2014.
• Please use the code under the GNU GPLv3
• Changelog:
  • Dec. 28, 2014: The MATLAB built-in function 'setdiff’ used for generating random connected graphs is replaced by customized code. This change makes v1.1 more than twice as fast as v1.0.
  • May 26, 2015: The input variable 'name’ is changed to be case insensitive. Cleared some unnecessary code snippets.
  • May 3, 2016: We add the function of generating connected regular graphs without requiring matgraph. The new version can generate regular graphs much more efficient than the previous version. Cleared some unnecessary code snippets.

Matlab code

• GGen2_v2.0
• GGen_v1.1
• GGen_v1.0