FETA (Framework for Evolving Topology Analysis) software

Model File Format

FETA models are defined by this file format.

The model comes in two parts, an outer model and an inner model.

The outer model describes what operation occurs on the network.

The inner model describes a probability model for the entity on which this operation occurs.

Currently the outer model operations can be:

1. Connect an edge from an existing node to a new node

2. Connect an edge between two existing nodes

These are matched to two inner models:

1. The new node model assigns probabilities to a node which will connect to the newest node in the network.

2. The inner edge model assigns probabilities to nodes, pairs of which will be connected.

Each line in the file begins either N, E, n, e or S A # indicates comments in the file. The S is used to indicate that the graph will be simple (no repeated edges between the same node pair).

Outer model file format

A line beginning n specifies the outer model for adding new nodes. The next lines are a probability distribution for the number of existing nodes the new node connects to. This line MUST be present.

n 0 0.1 0.2 0.3 0.3 0.1
# This says that a new node connects to
# 0 inner nodes with probability 0 (this must always be zero)
# 1 inner node with probability 0.1
# 2 inner nodes with probability 0.2
# 3 inner nodes with probability 0.3
# 4 inner nodes with probability 0.3
# 5 inner nodes with probability 0.1

A line beginning e describes the outer model for adding edges between existing nodes

e 0.1 0.4 0.5
# This says that after a new node has connected to all its edges
# 0 inner edges will follow with probability 0.1
# 1 inner edge will follow with probability 0.4
# 2 inner edges will follow with probability 0.5

There is no necessity for an outer model for internal edges to be present.

A line containing S means the graph produced will be “simple” (no repeated edges between the same node pair).

A line beginning N describes part of the inner model for choosing nodes to connect to a new node. The line has the form shown below. Several lines beginning with N can make up the inner model for nodes to connect to new nodes. At least one such line must be present and the probabilities must total 1.

N 1 0.5
N 3 0.5 0.004
# This specifies an inner model of type 1 with probability 0.5
# and an inner model of type 3 with probability 0.5 – the inner model type
# 3 (a PFP model) requires an extra parameter which is 0.004.

Similarly a line beginning with E specifies the inner model for choosing edges between existing nodes. This must be present if and only if the outer model for such edges (a line beginning ’e’) is present. Other than the change of letter it has the same form as above.

E 2 0.3
E 5 0.3
E 6 0.4

Inner model components

Node model components select what new nodes connect to lines have the form
N node_model_type parameter parms
or E node_model_type parameter parms

• Model 1 – equal probabilities (random)

• Model 2 – proportional to node degree (d)

• Model 3 – proportional to d^(1 + delta log10 d) – PFP, delta parameter must be specified

• Model 4 – nodes have equal prob if node is a singleton (degree 1) zero otherwise

• Model 5 – nodes have equal prob if node is a doubleton (degree 2) zero otherwise

• Model 6 – prob is proportional to triangle count

• Model 7 – prob is const if node has been selected in last N steps (N is parameter)

For model 4,5,6 if there are no nodes which are singleton/doubleton/have triangles then all nodes have equal probability.

Contact: Richard G. Clegg (richard@richardclegg.org)