generate Barabasi-Albert random graph
(optional) one or more options; see below
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.
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.
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.
G ≔ BarabasiAlbertGraph⁡8,3
G≔Graph 1: an undirected graph with 8 vertices and 15 edge(s)
The DegreeSequence command returns a list of degrees of the vertices for a given graph.
G ≔ BarabasiAlbertGraph⁡103,4
G≔Graph 2: an undirected graph with 1000 vertices and 3984 edge(s)
To view the degree distribution of a Barabási-Albert graph:
Generate a sequence of Barabási-Albert graphs with 20 initial vertices.
graphs ≔ seq⁡BarabasiAlbertGraph⁡100,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.
components ≔ map⁡BiconnectedComponents,graphs:
To view the distribution of the number of vertices in the bi-connected components.
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.
n ≔ numelems⁡components1
s ≔ ColorTools:-EvenSpread⁡ColorTools:-Color⁡Lab,red,n
s≔〈Lab : 47.9 35.2 -82〉,〈Lab : 33.8 79.7 -105〉,〈Lab : 51.9 91 -74.9〉,〈Lab : 55.6 86.6 -9.74〉,〈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〉
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.
The GraphTheory[RandomGraphs][BarabasiAlbertGraph] command was introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
Download Help Document
What kind of issue would you like to report? (Optional)