 GraphTheory/RandomGraphs/BarabasiAlbertGraph - Help

GraphTheory[RandomGraphs]

 BarabasiAlbertGraph
 generate Barabasi-Albert random graph

 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $G≔\mathrm{BarabasiAlbertGraph}\left(8,3\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 8 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$ The DegreeSequence command returns a list of degrees of the vertices for a given graph.

 > $\mathrm{DegreeSequence}\left(G\right)$
 $\left[{1}{,}{4}{,}{3}{,}{6}{,}{5}{,}{5}{,}{3}{,}{3}\right]$ (2)
 > $G≔\mathrm{BarabasiAlbertGraph}\left({10}^{3},4\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 1000 vertices and 3984 edge\left(s\right)}}$ (3)

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

 > $\mathrm{Statistics}:-\mathrm{Histogram}\left(\mathrm{DegreeSequence}\left(G\right),\mathrm{discrete}\right)$ Generate a sequence of Barabási-Albert graphs with 20 initial vertices.

 > $\mathrm{graphs}≔\left[\mathrm{seq}\left(\mathrm{BarabasiAlbertGraph}\left(100,2,\mathrm{initial}=20\right),1..100\right)\right]:$

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.

 > $\mathrm{components}≔\mathrm{map}\left(\mathrm{BiconnectedComponents},\mathrm{graphs}\right):$

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

 > $\mathrm{Statistics}:-\mathrm{Histogram}\left(\mathrm{map}\left(\mathrm{numelems},\mathrm{components}\right),\mathrm{discrete}\right)$ 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.

 > $\mathrm{components}\left[1\right]$
 $\left[\left[{21}{,}{2}\right]{,}\left[{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}\right]{,}\left[{21}{,}{4}\right]{,}\left[{21}{,}{6}\right]{,}\left[{21}{,}{12}\right]{,}\left[{21}{,}{16}\right]{,}\left[{21}{,}{19}{,}{24}\right]{,}\left[{21}{,}{20}\right]{,}\left[{1}{,}{21}\right]\right]$ (4)
 > $n≔\mathrm{numelems}\left(\mathrm{components}\left[1\right]\right)$
 ${n}{≔}{9}$ (5)
 > $s≔\mathrm{ColorTools}:-\mathrm{EvenSpread}\left(\mathrm{ColorTools}:-\mathrm{Color}\left("Lab","red"\right),n\right)$
 ${s}{≔}\left[{⟨}\colorbox[rgb]{0,0.4,1}{{Lab : 47.9 35.2 -82}}{⟩}{,}{⟨}\colorbox[rgb]{0.2,0,1}{{Lab : 33.8 79.7 -105}}{⟩}{,}{⟨}\colorbox[rgb]{0.8,0,1}{{Lab : 51.9 91 -74.8}}{⟩}{,}{⟨}\colorbox[rgb]{1,0,0.6}{{Lab : 55.7 86.5 -9.72}}{⟩}{,}{⟨}\colorbox[rgb]{1,0,0}{{Lab : 53.2 80.1 67.2}}{⟩}{,}{⟨}\colorbox[rgb]{1,0.6,0}{Lab : 72.3 30.2 77.2}{⟩}{,}{⟨}\colorbox[rgb]{0.8,1,0}{Lab : 93.6 -41.9 90.3}{⟩}{,}{⟨}\colorbox[rgb]{0.2,1,0}{Lab : 88.1 -83.1 83.6}{⟩}{,}{⟨}\colorbox[rgb]{0,1,0.4}{Lab : 88.2 -80.3 57.9}{⟩}\right]$ (6)
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{HighlightSubgraph}\left(\mathrm{graphs}\left[1\right],\mathrm{InducedSubgraph}\left(\mathrm{graphs}\left[1\right],\mathrm{components}\left[1\right]\left[i\right]\right),s\left[i\right],\mathrm{black}\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 > $\mathrm{DrawGraph}\left(\mathrm{graphs}\left[1\right],\mathrm{style}=\mathrm{spring}\right)$ 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.