edu.stanford.math.plex4.graph.random

Class BAGraph

java.lang.Object

edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

edu.stanford.math.plex4.graph.random.BAGraph

All Implemented Interfaces:

java.io.Serializable

public class BAGraph
extends GraphInstanceGenerator

Implements a Barabasi-Albert (BA) random graph model. From Wikipedia: The Barabasi-Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Scale-free networks are widely observed in natural and man-made systems, including the Internet, the world wide web, citation networks, and some social networks.

Author:

Tim Harrington

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

GraphInstanceGenerator.ImplementationType

Field Summary

Fields

Modifier and Type	Field and Description
protected int	mParam
protected int	nParam

Fields inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

graphImplementation, implementationType

Constructor Summary

Constructors

Constructor and Description
BAGraph(int n, int m)

Method Summary

Methods

Modifier and Type	Method and Description
AbstractUndirectedGraph	generate() This algorithm makes a power law graph with n nodes.
protected double[]	getProbabilityPartition(int[] d) Constructs a partition p of [0,1] such that p[i+1]-p[i] is proportional to the degree of node i in the list d.
protected AbstractUndirectedGraph	makeStarterGraph(int size, AbstractUndirectedGraph graph) Make a starter graph, in this case a line TODO: what kind of starter graph??
java.lang.String	toString()
protected int	whichSegmentHasX(double[] p, double x) Returns the segment i such that x is in [p[i],p[i+1]].

Methods inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

initializeGraph, setImplementationType

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

nParam

protected int nParam

mParam

protected int mParam

Constructor Detail

BAGraph

public BAGraph(int n,
       int m)

Method Detail

generate

public AbstractUndirectedGraph generate()

This algorithm makes a power law graph with n nodes. First it makes a connected starter graph with m nodes. Then it adds new nodes with up to m edges to existing nodes. An edge to node i is added with probability p_i = \frac{k_i}{\displaystyle\sum_j k_j}, where k_j is the degree of node j.

Specified by:

generate in class GraphInstanceGenerator

Parameters:

dataDimension - the size of the graph

numDataPoints - the number of potential edges to add at each step where m<

whichSegmentHasX

protected int whichSegmentHasX(double[] p,
                   double x)

Returns the segment i such that x is in [p[i],p[i+1]]. The partition p has n+1 values representing n segments. Therefore the returned value will always be between 0 and n-1.

Parameters:

p -

x -

Returns:

getProbabilityPartition

protected double[] getProbabilityPartition(int[] d)

Constructs a partition p of [0,1] such that p[i+1]-p[i] is proportional to the degree of node i in the list d. The return value p satisfies p[i] <= p[i+1], p[0]==0, and p[end] = 1.

Parameters:

d -

Returns:

makeStarterGraph

protected AbstractUndirectedGraph makeStarterGraph(int size,
                                       AbstractUndirectedGraph graph)

Make a starter graph, in this case a line TODO: what kind of starter graph??

Parameters:

numDataPoints -

Returns:

degree sum of the starter graph

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object