GraphTheory/RandomGraphs/BarabasiAlbertGraph - Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : GraphTheory/RandomGraphs/BarabasiAlbertGraph

GraphTheory[RandomGraphs]

  

BarabasiAlbertGraph

  

generate Barabasi-Albert random graph

 

Calling Sequence

Parameters

Options

Description

Definition

Examples

References

Compatibility

Calling Sequence

BarabasiAlbertGraph(n,m,opts)

Parameters

n,m

-

positive integers

opts

-

zero or more options; see below

Options

• 

initial : posint 

  

Number of initial vertices. The default value is m.

• 

seed : integer or none

  

Seed for the random number generator. If an integer is specified, this is equivalent to calling randomize(seed) immediately before invoking this function. The default is none.

Description

• 

BarabasiAlbertGraph(n,m,opts) creates a Barabási–Albert random graph with n vertices, in which each new vertex added after the initial step is connected to m existing vertices.

• 

The random number generator used can be seeded using the randomize function or the seed option.

Definition

• 

The Barabási–Albert model is an algorithm for generating random graphs which are scale-free. It begins with some number of initial vertices. Additional vertices are then added incrementally until there are n vertices. Each new vertex v is connected is connected to m existing vertices with a probability which is proportional to the degree of each existing vertex at the moment v is added.

Examples

withGraphTheory:

withRandomGraphs:

GBarabasiAlbertGraph8,3

GGraph 1: an undirected unweighted graph with 8 vertices and 15 edge(s)

(1)

DrawGraphG

The DegreeSequence command returns a list of degrees of the vertices for a given graph.

DegreeSequenceG

1,4,3,6,5,5,3,3

(2)

GBarabasiAlbertGraph103,4

GGraph 2: an undirected unweighted graph with 1000 vertices and 3984 edge(s)

(3)

To view the degree distribution of a Barabási-Albert graph:

Statistics:-HistogramDegreeSequenceG,discrete

Generate a sequence of Barabási-Albert graphs with 20 initial vertices.

graphsseqBarabasiAlbertGraph100,2,initial=20,1..100:

A graph is bi-connected if it is connected and removal of any vertex from the graph does not disconnect it. A maximal bi-connected subgraph is called a bi-connected component.

componentsmapBiconnectedComponents,graphs:

To view the distribution of the number of vertices in the bi-connected components.

Statistics:-Histogrammapnumelems,components,discrete

The graphs above typically have one large bi-connected component and several smaller ones that generally have degree 1. This can be visualized as follows for the first graph in the sequence.

components1

21,2,21,3,37,18,27,42,31,5,25,26,13,30,48,63,32,55,33,8,35,9,29,40,36,23,11,22,76,93,51,10,53,56,58,14,65,52,17,44,67,69,66,90,77,81,15,28,47,59,60,96,79,89,98,39,87,34,41,46,54,72,82,62,73,74,49,94,84,45,70,99,88,64,68,50,80,85,92,38,100,71,83,86,91,75,97,43,78,7,57,61,95,21,4,21,6,21,12,21,16,21,19,24,21,20,1,21

(4)

nnumelemscomponents1

n9

(5)

sColorTools:-EvenSpreadColorTools:-ColorLab,red,n

sLab : 47.9 35.2 -82,Lab : 33.8 79.7 -105,Lab : 51.9 91 -74.8,Lab : 55.7 86.5 -9.72,Lab : 53.2 80.1 67.2,Lab : 72.3 30.2 77.2,Lab : 93.6 -41.9 90.3,Lab : 88.1 -83.1 83.6,Lab : 88.2 -80.3 57.9

(6)

foritondoHighlightSubgraphgraphs1,InducedSubgraphgraphs1,components1i,si,blackenddo:

DrawGraphgraphs1,style=spring

References

  

Albert, Réka; Barabási, Albert-László (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. arXiv:cond-mat/0106096. Bibcode:2002RvMP...74...47A. CiteSeerX 10.1.1.242.4753. doi:10.1103/RevModPhys.74.47. ISSN 0034-6861.

Compatibility

• 

The GraphTheory[RandomGraphs][BarabasiAlbertGraph] command was introduced in Maple 2019.

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

DrawGraph

HighlightSubgraph

InducedSubgraph

RandomGraph