sample_fitness_pl: Scale-free random graphs, from vertex fitness scores

In igraph: Network Analysis and Visualization

Scale-free random graphs, from vertex fitness scores

Description

This function generates a non-growing random graph with expected power-law degree distributions.

Usage

sample_fitness_pl(
  no.of.nodes,
  no.of.edges,
  exponent.out,
  exponent.in = -1,
  loops = FALSE,
  multiple = FALSE,
  finite.size.correction = TRUE
)

Arguments

no.of.nodes	The number of vertices in the generated graph.
no.of.edges	The number of edges in the generated graph.
exponent.out	Numeric scalar, the power law exponent of the degree distribution. For directed graphs, this specifies the exponent of the out-degree distribution. It must be greater than or equal to 2. If you pass Inf here, you will get back an Erdős-Rényi random network.
exponent.in	Numeric scalar. If negative, the generated graph will be undirected. If greater than or equal to 2, this argument specifies the exponent of the in-degree distribution. If non-negative but less than 2, an error will be generated.
loops	Logical scalar, whether to allow loop edges in the generated graph.
multiple	Logical scalar, whether to allow multiple edges in the generated graph.
finite.size.correction	Logical scalar, whether to use the proposed finite size correction of Cho et al., see references below.

Details

This game generates a directed or undirected random graph where the degrees of vertices follow power-law distributions with prescribed exponents. For directed graphs, the exponents of the in- and out-degree distributions may be specified separately.

The game simply uses sample_fitness() with appropriately constructed fitness vectors. In particular, the fitness of vertex i is i^{-\alpha}, where \alpha = 1/(\gamma-1) and \gamma is the exponent given in the arguments.

To remove correlations between in- and out-degrees in case of directed graphs, the in-fitness vector will be shuffled after it has been set up and before sample_fitness() is called.

Note that significant finite size effects may be observed for exponents smaller than 3 in the original formulation of the game. This function provides an argument that lets you remove the finite size effects by assuming that the fitness of vertex i is (i+i_0-1)^{-\alpha} where i_0 is a constant chosen appropriately to ensure that the maximum degree is less than the square root of the number of edges times the average degree; see the paper of Chung and Lu, and Cho et al for more details.

Value

An igraph graph, directed or undirected.

Related documentation in the C library

igraph_static_power_law_game().

Author(s)

Tamas Nepusz [e-mail]

References

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

See Also

Random graph models (games) erdos.renyi.game(), sample_(), sample_bipartite(), sample_chung_lu(), sample_correlated_gnp(), sample_correlated_gnp_pair(), sample_degseq(), sample_dot_product(), sample_fitness(), sample_forestfire(), sample_gnm(), sample_gnp(), sample_grg(), sample_growing(), sample_hierarchical_sbm(), sample_islands(), sample_k_regular(), sample_last_cit(), sample_pa(), sample_pa_age(), sample_pref(), sample_sbm(), sample_smallworld(), sample_traits_callaway(), sample_tree()

Examples

g <- sample_fitness_pl(10000, 30000, 2.2, 2.3)
plot(degree_distribution(g, cumulative = TRUE, mode = "out"), log = "xy")

igraph documentation built on Oct. 20, 2024, 1:06 a.m.