Archive for the ‘Graph Generator’ Category

Integer sequence discovery from small graphs

Monday, February 23rd, 2015

Integer sequence discovery from small graphs by Travis Hoppe and Anna Petrone.

Abstract:

We have exhaustively enumerated all simple, connected graphs of a finite order and have computed a selection of invariants over this set. Integer sequences were constructed from these invariants and checked against the Online Encyclopedia of Integer Sequences (OEIS). 141 new sequences were added and 6 sequences were appended or corrected. From the graph database, we were able to programmatically suggest relationships among the invariants. It will be shown that we can readily visualize any sequence of graphs with a given criteria. The code has been released as an open-source framework for further analysis and the database was constructed to be extensible to invariants not considered in this work.

See also:

Encyclopedia of Finite Graphs “Set of tools and data to compute all known invariants for simple connected graphs”

Simple-connected-graph-invariant-database “The database file for the Encyclopedia of Finite Graphs (simple connected graphs up to order 10)”

From the paper:

A graph invariant is any property that is preserved under isomorphism. Invariants can be simple binary properties (planarity), integers (automorphism group size), polynomials (chromatic polynomials), rationals (fractional chromatic numbers), complex numbers (adjacency spectra), sets (dominion sets) or even graphs themselves (subgraph and minor matching).

Hmmm, perhaps an illustration, also from the paper, might explain better:

invariant

Figure 1: An example query to the Encyclopedia using speci c invariant conditions. The command python viewer.py 10 -i is bipartite 1 -i is integral 1 -i is eulerian 1 displays the three graphs that are simultaneously bipartite, integral and Eulerian with ten vertices.

For analysis of “cells” of your favorite evil doers you can draw higgly-piggly graphs with nodes and arcs on a whiteboard or you can take advantage of formal analysis of small graphs, research on the organization of small groups, and the history of that particular group. With the higgly-piggly approach you risk missing connections that aren’t possible to represent from your starting point.

Pattern Based Graph Generator

Monday, March 4th, 2013

Pattern Based Graph Generator by Hong-Han Shuai, De-Nian Yang, Philip S. Yu, Chih-Ya Shen, Ming-Syan Chen.

Abstract:

The importance of graph mining has been widely recognized thanks to a large variety of applications in many areas, while real datasets always play important roles to examine the solution quality and efficiency of a graph mining algorithm. Nevertheless, the size of a real dataset is usually fixed and constrained according to the available resources, such as the efforts to crawl an on-line social network. In this case, employing a synthetic graph generator is a possible way to generate a massive graph (e.g., billions nodes) for evaluating the scalability of an algorithm, and current popular statistical graph generators are properly designed to maintain statistical metrics such as total node degree, degree distribution, diameter, and clustering coefficient of the original social graphs. Nevertheless, in addition to the above metrics, recent studies on graph mining point out that graph frequent patterns are also important to provide useful implications for the corresponding social networking applications, but this crucial criterion has not been noticed in the existing graph generators. This paper first manifests that numerous graph patterns, especially large patterns that are crucial with important domain-specific semantic, unfortunately disappear in the graphs created by popular statistic graph generators, even though those graphs enjoy the same statistical metrics with the original real dataset. To address this important need, we make the first attempt to propose a pattern based graph generator (PBGG) to generate a graph including all patterns and satisfy the user-specified parameters on supports, network size, degree distribution, and clustering coefficient. Experimental results show that PBGG is efficient and able to generate a billion-node graph with about 10 minutes, and PBGG is released for free download.

Download at: http://arbor.ee.ntu.edu.tw/~hhshuai/PBGG.html.

OK, this is not a “moderate size database” program.