0001 function ssca2stats (inscale, seed)
0002 % SSCA2STATS - Generate SSCA#2 graph statistics
0003 % 
0004 % Usage: ssca2stats (scale)
0005 %        ssca2stats (scale, seed)
0006 %
0007 % The RNG can be seeded using the seed argument. If seed is [],
0008 % then the current time is used to seed the RNG.
0009 % To generate statistics for all graphs of scales 1 to 30
0010 %    ssca2stats (1:30) 
0011 %
0012 % The procedure to generate graph statistics closely mirrors the
0013 % data generator.
0014 %
0015 % Viral Shah (c) 2006. All rights reserved.
0016 %
0017 %%
0018 %
0019 % SCALE     #VERTICES  #CLIQUES           #EDGES          #EDGES
0020 %                                     UNDIRECTED        DIRECTED
0021 % --------------------------------------------------------------
0022 %  1                2         2                0               0
0023 %  2                4         4                0               0
0024 %  3                8         5                7              24
0025 %  4               16        10               18              63
0026 %  5               32        16               46             163
0027 %  6               64        28              109             391
0028 %  7              128        41              267             960
0029 %  8              256        77              602            2166
0030 %  9              512       111             1526            5491
0031 % 10             1024       186             3670           13212
0032 % 11             2048       316             8549           30775
0033 % 12             4096       496            21490           77364
0034 % 13             8192       750            56095          201942
0035 % 14            16384      1250           135643          488313
0036 % 15            32768      2020           344116         1238815
0037 % 16            65536      3158           868234         3125641
0038 % 17           131072      5202          2167232         7802034
0039 % 18           262144      8052          5554752        19997106
0040 % 19           524288     13045         13869175        49929030
0041 % 20          1048576     20643         35052403       126188649
0042 % 21          2097152     32481         88660890       319179204
0043 % 22          4194304     51747        224308304       807509893
0044 % 23          8388608     82387        565023822      2034085758
0045 % 24         16777216    130664       1426509164    5.135433e+09
0046 % 25         33554432    207082     3.597598e+09    1.295135e+10
0047 % 26         67108864    329513     9.071187e+09    3.265627e+10
0048 % 27        134217728    523245     2.286679e+10    8.232044e+10
0049 % 28        268435456    830781     5.761495e+10    2.074138e+11
0050 % 29        536870912   1320536     1.451709e+11    5.226152e+11
0051 % 30       1073741824   2096264     3.660036e+11    1.317613e+12
0052 
0053 
0054 
0055 if nargin < 2
0056     seed = 1;
0057 elseif isempty(seed)
0058     seed = sum(100*clock);
0059 end
0060 rand('state',seed);
0061 
0062 fprintf ('\n');
0063 fprintf ('SCALE     #VERTICES  #CLIQUES           #EDGES          #EDGES\n');
0064 fprintf ('                                    UNDIRECTED        DIRECTED\n');  
0065 fprintf ('--------------------------------------------------------------\n');
0066 
0067 for scale = inscale
0068 
0069   % Parameters
0070   TotVertices = 2.^scale;
0071   ProbInterCliqueEdges = 0.5;
0072   ProbUniDirectional = 0.2;
0073   MaxParallelEdges = 3;
0074   MaxCliqueSize = floor(2.^(scale/3));
0075   
0076   % Count number of cliques and clique sizes 
0077   ncliques = ceil(2*TotVertices/MaxCliqueSize);
0078   cliquesizes = 0;
0079   while sum(cliquesizes) < TotVertices
0080     ncliques = round(1.05 * ncliques + 1);
0081     cliquesizes = 1 + fix(MaxCliqueSize * rand(1,ncliques));
0082   end
0083   firstvtx = cumsum([1 cliquesizes]);
0084   ncliques = min(find(firstvtx > TotVertices)) - 1;
0085   firstvtx = firstvtx(1:ncliques);
0086   cliquesizes = diff([firstvtx TotVertices+1]);
0087   ncliques = length(cliquesizes);
0088 
0089   % Count edges within cliques 
0090   cedges = sum((cliquesizes .* (cliquesizes-1))/2);
0091   
0092   % Count edges between cliques
0093   possibles = [];
0094   for dist = 2.^(1:(scale-2));
0095     prob = ProbInterCliqueEdges * (2 / dist);
0096     possibleedges = cliquesizes;
0097     possibleedges (cliquesizes > dist) = dist;
0098     possibles = [possibles fix(prob*sum(possibleedges))];
0099   end
0100   uedges = cedges + sum (possibles);
0101 
0102   % Count edges accounting for unidirectional and bidirectional edges
0103   dedges = fix((1 + (1-ProbUniDirectional)) * uedges);
0104 
0105   % Count edges accounting for duplicates 
0106   pedges = dedges;
0107   nnew = pedges;
0108   for dups = 2:MaxParallelEdges;
0109     prob = (MaxParallelEdges-dups+1) ./ (MaxParallelEdges-dups+2);
0110     nnew = fix(prob * nnew);
0111     pedges = pedges + nnew;
0112   end
0113 
0114   fprintf ('%2d  %15d  %8d  %15d %15d\n', ...
0115        scale, ...
0116        TotVertices, ...
0117        ncliques, ...
0118        uedges, ...
0119        pedges);
0120 
0121 end
0122 
0123 fprintf ('\n');