TopGen and TopAnalysis

In the paper "Improved Tradeoff-based Models of the Internet" we used two programs, TopGen and TopAnalysis, to generate and analyze  internet topologies. Here we make both available.

If you decide to cite our tool or paper, please use the below Bibtex entry:
  author= {Antonis Spatharis and Ilias Foudalis and Minas Gjoka and Panagiota Krouska and Christos Amanatidis and  Christos H. Papadimitriou and Martha Sideri},
  title= {{Improved Tradeoff-based Models of the Internet}},
  booktitle = {Proceedings of the SIWN/IEEE International Conference on Complex Open Distributed Systems (CODS '07)},
  address = {Chengdu, China},
  month = {July},
  year = {2007}

TopGen and TopAnalysis are two programs made available to users that want to evaluate internet modeling algorithms like BA (Barabasi-Albert [1]) variants and FKP (Fabricant, Koutsoupias and Papadimitriou [2]). TopGen is mainly used to generate a graph and also implements some basic metrics. It supports the following models: FKP, Uniform, Probabilistic, DeGen, ProbiGen, Best Two, Independent Path, Fertile Node, AHOT – 2, Controlled Distance, Enhanced BT.  [3] contains more information on the last six models. TopAnalysis is used to load an already existing graph and evaluate it using different metrics.

TopGen is written by Minas Gjoka, Foudalis Ilias and Krouska Giwta. TopAnalysis is written by Minas Gjoka. Notable libraries used are :

1) Colt, an open source library for High Performance Scientific and Technical Computing

2) JUNG, the Java Universal Network/Graph Framework


Both programs use Java 1.4. Use “winrun.bat” and “linuxrun” to run the programs in Windows or UNIX/Linux accordingly.


    First, select the model that you want to use from the “Network Model” tabbed pane. Then set the models parameters at “Model Params” and “Graph Params” tabbed panes. After these steps, you can run/create your graph. You have two options. Either you can run it Step by Step (by pressing the step by step button and then the >> to go to the next step) or by pressing the graph generation button. These buttons can be found in the Graph Operations pane.

Note that if you want to run the BT model you have to set MaxEdgesPerStep = 2.


    TopGen also implements some graph metrics such as Frequency vs. Degree and Degree vs. Rank power laws. Also for the Controlled Distance model the Average Distance vs. Degree metric is supported. Another very useful operation (especially, if you are planning to use the TopAnalysis program) is the "Graph Data" button at the "Graph Operations" pane. There you can find an option to export your data to a file. After that you can load the data from TopAnalysis and analyze the graph. A useful option if you always want to have random graphs created is to check the “Use Randomize” box that can be found at “Randomiz.Method” tabbed pane. It should be noted that TopGen contains many more features not mentioned in this brief introduction. Some screenshots from TopGen follow below

topgen FKP image
topgen IP iamge topgen CD image

First you have to open a graph file. The formats of the following generators are supported:

i)  TopGen with extension .topgen (see section 3.2 to see how you can save a graph file).
ii) BGP Table Dump with extension .txt
iii) Inet with extension .inet
iv) ToGenD with extension .togend
v) GDTANG with extension .gdtang
vi) Dreier wtih extension .dreir

When the graph is loaded, click on the 2 metric menus and select the metric that you want to do.

Note that the information for the metrics may being printed in the console. Only the graphs (if they exist on the specific metric) are presented in the main program.

A list with the implemented graph metrics follows. Snapshots are included for a FKP generated topology with 500 nodes and 975 edges (or file "testinput2.topgen" inside the released TopAnalysis archive ). 

a) Degree vs Rank,  Frequency vs Degree, CCDF vs Degree

Console Output:

Intercept 49.090476190476195
Correlation -0.9628887480176338

Semi-Log Slope -0.03763658011161233
Semi-Log Intercept 1.8943662136549848
Semi-Log Correlation -0.9490372610950915

Log-Log Slope -0.9080111851577138
Log-Log Intercept 2.246603672934342
Log-Log Correlation -0.816719408941676

b) Adjacency Matrix Graph and Eigenvalues

adjacency matrix0adjacency eigen

c) Normalized Laplacian Matrix Eigenvalues


d) Eccentricity vs Degree, Average Path Length per Node

Console Output:
Radius: 4.0
Diameter: 7.0
Average Eccentricity: 5.732
Characteristic Path Length : 3.789234468937876
Center Size Ratio: 0.014
Min Degree in Center: 19
Periphery Size Ratio: 0.078
Max Degree in Periphery: 1


e) Neighborhood function

Console Output:
Time for neighbourhood function :159 ms
Characteristic Path Length = 3.7892344
Number of Vertexes within distance 0 : 1.0
Number of Vertexes within distance 1 : 4.9
Number of Vertexes within distance 2 : 50.364
Number of Vertexes within distance 3 : 190.92
Number of Vertexes within distance 4 : 378.588
Number of Vertexes within distance 5 : 483.904
Number of Vertexes within distance 6 : 499.496
Number of Vertexes within distance 7 : 500.0

f) Clustering vs Degree

Console Output:
<k> : 3.900000000000001
<k^2> : 69.66000000000001

Mean Local Clustering : 0.3478533033573012
PK Clustering : 0.0018358367470793495
K Clustering : 0.007800000000000001


g) Joint Degree Distribution

Console Output:
Average Neighbor Degree: 0.02966854568329395
Max Neighbor Degree: 0.059879374132881164

avgneighbor connectivity

h) Rich Club Connectivity

rich club

i)  Betweenness

Console Output:
Central Vertex Betweenness for 0:0.319546161953925
Central Vertex Betweenness for 1:0.029826686442693574
Central Vertex Betweenness for 2:0.07520265784472274
Central Vertex Betweenness for 3:0.1783896420339222 
Central Edge Betweenness for 0:0.02716926078618874     
Central Edge Betweenness for 1:0.0025821705168104885   
Central Edge Betweenness for 2:0.05112945369919995     
Central Edge Betweenness for 3:0.01710598777656324     

j) Export to METIS

METIS is a graph partitioning software found here.

k) Minimum Vertex Cover

Console Output:
VC Size:136
[469, 415, 190, 470, 31, 95, 86, 32, 225, 124, 96, 317, 1, 396, 288, 347, 481, 309, 100, 68, 378, 119, 226, 3, 81, 172, 27, 402, 2, 38, 57, 120, 126, 136, 168, 23, 87, 7, 54, 489, 53, 65, 424, 6, 132, 116, 93, 372, 4, 195, 410, 383, 114, 26, 55, 282, 362, 236, 204, 420, 74, 238, 46, 301, 384, 5, 15, 272, 368, 43, 143, 16, 80, 251, 187, 144, 176, 398, 188, 252, 14, 142, 131, 47, 442, 75, 465, 231, 175, 209, 487, 66, 103, 98, 44, 17, 205, 156, 461, 392, 357, 185, 37, 151, 8, 40, 99, 182, 483, 49, 391, 296, 134, 9, 334, 137, 21, 221, 179, 42, 90, 111, 19, 139, 11, 91, 39, 109, 92, 220, 20, 110, 404, 10, 0, 69]


Sometimes when new tabs are opened (a metric tab) and a graph has been generated, the graphics of the graph that has been drawn “break”. Sometimes you can fix the graphics if you open/close again the tab.


[1] R Albert, AL Barabasi, "Topology of evolving networks: local events and universality," Physical Review Letters, volume 85, pages 5234 - 237, 2000.

[2] Alex Fabrikant, Elias Koutsoupias and Christos H. Papadimitriou, "Heuristically Optimized Trade-offs: A new paradigm for power laws in the Internet," in Proceedings of the 29th International Colloquium on Automata, Languages and Programming, 2002.

[3] Antonis Spatharis, Ilias Foudalis, Minas Gjoka, Panagiota Krouska, Christos Amanatidis, Christos H. Papadimitriou, and Martha Sideri, "Improved Tradeoff-based Models of the Internet," in Proceedings of the SIWN/IEEE International Conference on Complex Open Distributed Systems 2007.