Type Alias Graph 

pub type Graph = igraph_t;

An igraph graph (igraph_t), see the module docs.

Aliased Type

pub struct Graph { /* private fields */ }

Implementations

impl Graph

pub fn transitivity_undirected(&self, mode: TransitivityMode) -> Result<f64>

Global transitivity (clustering coefficient) of the graph.

The transitivity is the probability that two neighbors of a vertex are connected; more precisely, it is the ratio between the number of closed connected triples (three times the number of triangles) and the number of connected triples. Edge directions and multiplicities are ignored. This single number differs from the average local transitivity, which weights all vertices equally.

mode says what to return for graphs without connected triples: TransitivityMode::Nan gives NaN, TransitivityMode::Zero gives 0.

Binds igraph_transitivity_undirected. Reference: S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press (1994).

See also Graph::count_triangles: for a simple graph with degrees d_v, the transitivity is 3 T / Σ_v d_v (d_v - 1) / 2.

Time complexity: O(|V| d²), d being the average degree.

Examples

use igraph::prelude::*;

// A triangle with a pendant edge: 3 closed triples out of 5.
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3)], 4, false)?;
assert!((g.transitivity_undirected(TransitivityMode::Nan)? - 0.6).abs() < 1e-12);

// A path has connected triples but no triangle; a single edge has neither.
let path = Graph::from_edges(&[(0, 1), (1, 2)], 3, false)?;
assert_eq!(path.transitivity_undirected(TransitivityMode::Nan)?, 0.0);
let edge = Graph::from_edges(&[(0, 1)], 2, false)?;
assert!(edge.transitivity_undirected(TransitivityMode::Nan)?.is_nan());
assert_eq!(edge.transitivity_undirected(TransitivityMode::Zero)?, 0.0);

pub fn transitivity_local_undirected<'a>( &self, vids: impl Into<VertexSelector<'a>>, mode: TransitivityMode, ) -> Result<Vec<f64>>

Local transitivity (clustering coefficient) of the selected vertices.

For each vertex, the fraction of pairs of its neighbors that are themselves connected (Watts–Strogatz clustering coefficient). Edge directions and multiplicities are ignored. Vertices with fewer than two neighbors get NaN with TransitivityMode::Nan and 0 with TransitivityMode::Zero. The result follows the order of vids.

Binds igraph_transitivity_local_undirected. Reference: D. J. Watts and S. Strogatz, Collective dynamics of small-world networks, Nature 393, 440–442 (1998).

See also Graph::count_adjacent_triangles: in a simple graph the local transitivity of v is t_v / (d_v (d_v - 1) / 2), t_v being the number of triangles through v.

Time complexity: O(n d²), n being the number of selected vertices and d the average degree.

Errors

ErrorKind::InvalidVertexId if the selector contains a non-existent vertex.

Examples

use igraph::prelude::*;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3)], 4, false)?;
let c = g.transitivity_local_undirected(.., TransitivityMode::Zero)?;
assert_eq!(c[..2], [1.0, 1.0]);
assert!((c[2] - 1.0 / 3.0).abs() < 1e-12);
assert_eq!(c[3], 0.0); // a leaf

pub fn transitivity_avglocal_undirected( &self, mode: TransitivityMode, ) -> Result<f64>

Average local transitivity (average clustering coefficient).

The mean of the local transitivities of all vertices. Vertices with fewer than two neighbors are left out of the average with TransitivityMode::Nan (the result is NaN if no vertex has two neighbors), and counted as zero with TransitivityMode::Zero. Edge directions and multiplicities are ignored.

Binds igraph_transitivity_avglocal_undirected. Reference: D. J. Watts and S. Strogatz, Collective dynamics of small-world networks, Nature 393, 440–442 (1998). A small-world graph (e.g. Graph::watts_strogatz_game with a small rewiring probability) has a much higher average clustering than an Erdős–Rényi graph of the same density.

Time complexity: O(|V| d²).

Examples

use igraph::prelude::*;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3)], 4, false)?;
// Local values: 1, 1, 1/3 and (leaf) NaN or 0.
let skip = g.transitivity_avglocal_undirected(TransitivityMode::Nan)?;
let zero = g.transitivity_avglocal_undirected(TransitivityMode::Zero)?;
assert!((skip - 7.0 / 9.0).abs() < 1e-12);
assert!((zero - 7.0 / 12.0).abs() < 1e-12);

pub fn transitivity_barrat<'a>( &self, vids: impl Into<VertexSelector<'a>>, weights: Option<&[f64]>, mode: TransitivityMode, ) -> Result<Vec<f64>>

Barrat’s weighted local transitivity of the selected vertices.

For a vertex i, every triangle i, j, h contributes the total weight w_ij + w_ih of the two triangle edges incident on i (in equation (5) each triangle appears twice, as the ordered pairs (j, h) and (h, j), with the mean weight (w_ij + w_ih) / 2); the sum is divided by s_i (k_i - 1), where s_i is the strength and k_i the degree of i (equation (5) of A. Barrat, M. Barthélemy, R. Pastor-Satorras and A. Vespignani, The architecture of complex weighted networks, PNAS 101, 3747 (2004)). With equal weights it coincides with the unweighted local transitivity.

Edge directions are ignored; the graph must not have multi-edges (for directed graphs, not even mutual pairs u -> v, v -> u, which become multi-edges once directions are ignored). If weights is None, igraph emits a warning and falls back to the unweighted local transitivity. When the denominator s_i (k_i - 1) is zero (fewer than two incident edges, or zero strength), TransitivityMode::Zero gives 0, while TransitivityMode::Nan performs the division: NaN (0 / 0), or ±∞ if a zero strength comes from weights of mixed signs around closed triangles.

Binds igraph_transitivity_barrat. See also Graph::strength for the s_i.

Time complexity: O(|V| d²).

Errors

ErrorKind::InvalidValue if the weight vector has the wrong length or the graph has multi-edges (or mutual directed edges); ErrorKind::InvalidVertexId for invalid vertices.

Examples

use igraph::prelude::*;

// igraph's unit test graph: two triangles 0-1-2 and 1-2-3, a tail 3-4, isolated 5.
let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)], 6, false)?;
let w = [-1.0, 0.0, 1.0, 2.0, 3.0, 4.0];
let t = g.transitivity_barrat(.., Some(&w), TransitivityMode::Zero)?;
let expected = [1.0, 0.75, 0.625, 0.277778, 0.0, 0.0];
for (a, b) in t.iter().zip(expected) {
    assert!((a - b).abs() < 1e-6);
}

pub fn ecc<'a>( &self, eids: impl Into<EdgeSelector<'a>>, k: usize, offset: bool, normalize: bool, ) -> Result<Vec<f64>>

Edge clustering coefficient of the selected edges.

For an edge (i, j), let z be the number of k-cycles it belongs to and s the largest such number compatible with the degrees of its endpoints: s = min(d_i - 1, d_j - 1) for k = 3 and s = (d_i - 1)(d_j - 1) for k = 4. The coefficient is

C = (z + offset) / s      (normalize = true)
C =  z + offset           (normalize = false)

where offset is 1 if offset is true and 0 otherwise. The original definition of Radicchi et al. (PNAS 101, 2658 (2004)) uses offset = true, normalize = true; with offset = false the normalized value is at most 1, which for k = 3 is achieved by every edge of a complete graph. When normalizing, edges with s = 0 (an endpoint of degree 1, or a self-loop, which igraph assigns z = s = 0) get NaN without offset (0 / 0) and +∞ with it (1 / 0). Multiplicities are ignored when listing cycles but not in the degrees. The result follows the order of eids.

Only k = 3 and k = 4 are currently supported.

Binds igraph_ecc. See also Graph::list_triangles (for k = 3, the unnormalized, offset-free coefficient of an edge is the number of listed triangles containing it) and Graph::community_edge_betweenness, the other classic edge-removal criterion for divisive community detection.

Time complexity: O(|V| d log d + |E| d) for k = 3, O(|V| d log d + |E| d²) for k = 4.

Errors

ErrorKind::InvalidValue if k < 3; ErrorKind::Unimplemented if k > 4; ErrorKind::InvalidEdgeId for invalid edges.

Examples

use igraph::prelude::*;

// In K4 each edge is in 2 triangles, the most its degree-3 endpoints allow.
let k4 = Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)], 4, false)?;
assert!(k4.ecc(.., 3, false, true)?.iter().all(|&c| c == 1.0));
assert_eq!(k4.ecc(0, 3, true, false)?, vec![3.0]); // 2 triangles, plus one

pub fn assortativity( &self, weights: Option<&[f64]>, values: &[f64], values_in: Option<&[f64]>, directed: bool, normalized: bool, ) -> Result<f64>

Assortativity coefficient based on numeric vertex values.

With normalized = true this is the Pearson correlation of the values x found at the two ends of the edges (Newman’s assortativity coefficient, in [-1, 1]); with normalized = false it is the covariance

cov(x_out, x_in) = 1/m Σ_ij (A_ij - k_i^out k_j^in / m) x_i x_j

For directed graphs (with directed = true) the value of the edge source is taken from values and the one of the target from values_in, if given (otherwise from values as well). Undirected graphs (and directed ones with directed = false) are treated as directed graphs with every edge reciprocated, so self-loops count twice; in that case values_in is ignored, with a warning if given. directed is ignored for undirected graphs.

When weights are given they act as edge multiplicities: m becomes the total weight and degrees become strengths.

Binds igraph_assortativity. See also Graph::assortativity_degree (values = degrees) and Graph::strength (weighted degrees as values). References: M. E. J. Newman, Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003); Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002).

Time complexity: O(|E|).

Errors

ErrorKind::InvalidValue if a value or weight vector has the wrong length.

Examples

use igraph::prelude::*;

// A path 0-1-2-3 with values increasing along it: neighbors are alike.
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], 4, false)?;
let r = g.assortativity(None, &[1.0, 2.0, 3.0, 4.0], None, false, true)?;
assert!(r > 0.0);
// Alternating values: every edge joins a "low" and a "high" vertex.
let r = g.assortativity(None, &[0.0, 1.0, 0.0, 1.0], None, false, true)?;
assert!((r + 1.0).abs() < 1e-12);

pub fn assortativity_nominal( &self, types: &[igraph_int_t], directed: bool, normalized: bool, ) -> Result<f64>

Assortativity coefficient based on vertex categories.

types[v] is the (non-negative integer) category of vertex v. The normalized coefficient (normalized = true, the usual choice) is 1 when all edges stay within categories, -1 for a perfectly disassortative network, and asymptotically 0 for random connections. The unnormalized version equals the modularity of the partition into categories (with resolution 1):

Q = 1/m Σ_ij (A_ij - k_i^out k_j^in / m) δ(t_i, t_j)

and the normalized one is Q divided by its largest possible value 1 - 1/m² Σ_ij k_i^out k_j^in δ(t_i, t_j), i.e. Q / (1 - Σ_t a_t b_t) with a_t (b_t) the fraction of edges starting (ending) in category t. (The C documentation of 1.0.1 writes this denominator as 1/m Σ_ij (m - k_i^out k_j^in δ(t_i, t_j) / m), which is not what the code computes.)

directed says whether to consider edge directions (ignored for undirected graphs, which are treated as directed graphs with reciprocal edges, so self-loops count twice). The null graph gives NaN.

Weighted nominal assortativity is not implemented by igraph (1.0.0 and 1.0.1 fail with IGRAPH_UNIMPLEMENTED when weights are given), so this wrapper takes no weights; use Graph::modularity for the weighted unnormalized value.

Binds igraph_assortativity_nominal. Reference: M. E. J. Newman, Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003).

Time complexity: O(|E| + t), t being the number of categories.

See also Graph::joint_type_distribution, the full mixing matrix of the categories.

Errors

ErrorKind::InvalidValue if types does not have one entry per vertex or contains negative values.

Examples

use igraph::prelude::*;

// Two triangles joined by one bridge; categories = triangles.
let g = Graph::from_edges(
    &[(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (2, 3)], 6, false)?;
let r = g.assortativity_nominal(&[0, 0, 0, 1, 1, 1], false, true)?;
assert!(r > 0.7);
// A bipartite labeling of a bipartite graph is perfectly disassortative.
let square = Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 0)], 4, false)?;
let r = square.assortativity_nominal(&[0, 1, 0, 1], false, true)?;
assert!((r + 1.0).abs() < 1e-12);

pub fn assortativity_degree(&self, directed: bool) -> Result<f64>

Degree assortativity: do high-degree vertices link to each other?

The assortativity coefficient with the vertex degrees as values, normalized (Pearson correlation of the degrees at the two ends of the edges). With directed = true on a directed graph, out-degrees are used for edge sources and in-degrees for edge targets; otherwise total degrees are used. Social networks tend to be assortative (> 0), technological and biological ones disassortative (< 0). For regular graphs the correlation is undefined and the result is NaN.

Binds igraph_assortativity_degree. Loops count twice in the degrees and multi-edges are counted with their multiplicity; the unnormalized covariance can be obtained with Graph::assortativity and Graph::strength values.

See also Graph::avg_nearest_neighbor_degree and Graph::degree_correlation_vector, which show the degree correlation as a function of the degree instead of summarizing it in one number.

Time complexity: O(|E| + |V|).

Examples

use igraph::prelude::*;

// In a star, the hub is only linked to leaves: perfectly disassortative.
let star = Graph::from_edges(&[(0, 1), (0, 2), (0, 3), (0, 4)], 5, false)?;
assert!((star.assortativity_degree(false)? + 1.0).abs() < 1e-12);
// A cycle is regular: the coefficient is undefined.
let c = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], 3, false)?;
assert!(c.assortativity_degree(false)?.is_nan());

pub fn joint_degree_matrix( &self, weights: Option<&[f64]>, max_out_degree: Option<usize>, max_in_degree: Option<usize>, ) -> Result<Matrix>

Joint degree matrix: number (or total weight) of edges between degree classes.

Entry (i - 1, j - 1) of the result holds J_ij, the number of edges (or the total weight, if weights are given) between vertices of (out-)degree i and vertices of (in-)degree j. Each edge, self-loops included, is counted exactly once: for ordered degree pairs (i, j) in directed graphs, whose entries then sum to the number of edges m (or total weight), and for unordered pairs in undirected graphs, whose matrix is symmetric and whose upper triangle (diagonal included) sums to m (without limits; with limits, only the part that fits). J_ij / m is the probability that a random edge joins degrees i and j.

max_out_degree / max_in_degree set the number of rows / columns; None uses the largest (out-/in-)degree of the graph. Edges whose degree pair falls outside the matrix are not counted. Unlike joint_degree_distribution, there is no row or column for degree zero, and undirected same-degree connections are counted once instead of twice.

Binds igraph_joint_degree_matrix. It is a finer description of a network than its degree sequence: degree-preserving rewiring keeps the degrees but in general changes this matrix. See also joint_degree_distribution. Reference: I. Stanton and A. Pinar, Constructing and sampling graphs with a prescribed joint degree distribution, ACM J. Exp. Algorithmics 17, 3.5 (2012).

Time complexity: O(|E|).

Errors

ErrorKind::InvalidValue if the weight vector has the wrong length or a limit does not fit an i64.

Examples

use igraph::prelude::*;

// A star with 3 leaves: 3 edges between degree 3 and degree 1.
let star = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], 4, false)?;
let j = star.joint_degree_matrix(None, None, None)?;
assert_eq!(j.to_rows(), vec![
    vec![0.0, 0.0, 3.0],
    vec![0.0, 0.0, 0.0],
    vec![3.0, 0.0, 0.0],
]);

pub fn joint_degree_distribution( &self, weights: Option<&[f64]>, options: &JointDegreeDistributionOptions, ) -> Result<Matrix>

Joint degree distribution P_ij of connected vertex pairs.

Entry (i, j) is the probability that a randomly chosen ordered pair of connected vertices u -> v has degrees i (for u, computed with from_mode) and j (for v, computed with to_mode). An undirected graph behaves like the directed graph with all edges reciprocated. Without normalization the entries are connection counts (or total weights): without degree limits they sum to the number of edges of a directed graph (twice that with directed_neighbors = false) and to twice that of an undirected one. Rows and columns for degree 0 are included.

Related quantities: the degree correlation function is k_nn(k) = Σ_j j P_kj / Σ_j P_kj and the unnormalized degree assortativity is Σ_ij i j (P_ij - q_i r_j) with q and r the row and column sums. Compare with joint_degree_matrix, whose undirected diagonal is half of the unnormalized P_ii.

When connections are counted in both directions (undirected graphs, or directed_neighbors = false), each reverse connection v -> u contributes to entry (deg_from(v), deg_to(u)) if it falls within the matrix, and normalization divides by the total weight of the connections that fall within it. In the cases where igraph 1.0.0 and 1.0.1 would index out of bounds (non-square limits, or from_mode != to_mode without directed_neighbors), this wrapper computes the matrix in Rust with exactly these semantics.

Binds igraph_joint_degree_distribution. See also Graph::degree_correlation_vector, which computes k_nn(k) directly, and Graph::assortativity with degree values.

Time complexity: O(|E|).

Errors

ErrorKind::InvalidValue if the weight vector has the wrong length or a degree limit is i64::MAX or more.

Examples

use igraph::mixing::JointDegreeDistributionOptions;
use igraph::prelude::*;

let star = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], 4, false)?;
let p = star.joint_degree_distribution(None, &JointDegreeDistributionOptions::default())?;
assert_eq!(p.shape(), (4, 4));
// Half of the ordered pairs go hub -> leaf, half leaf -> hub.
assert_eq!(p[(3, 1)], 0.5);
assert_eq!(p[(1, 3)], 0.5);

pub fn joint_type_distribution( &self, weights: Option<&[f64]>, from_types: &[igraph_int_t], to_types: Option<&[igraph_int_t]>, directed: bool, normalized: bool, ) -> Result<Matrix>

Mixing matrix of vertex categories.

Entry (i, j) is proportional to the probability that a randomly chosen ordered pair of connected vertices u -> v has from_types[u] = i and to_types[v] = j (to_types = None reuses from_types). Types must be non-negative integers; the matrix has one more row/column than the largest source/target type, so re-index sparse labels first. Undirected graphs (or directed = false) count each edge in both directions. With normalized = true the entries sum to 1; otherwise they are connection counts (or total weights). When connections are counted in both directions, the reverse connection v -> u of an edge contributes to (from_types[v], to_types[u]); with distinct to_types this case is computed in Rust, because igraph 1.0.0 and 1.0.1 would index out of bounds.

With a single normalized categorization M, row sums a and column sums b, the modularity of the partition is Q = Σ_i M_ii - Σ_i a_i b_i and the nominal assortativity is Q / (1 - Σ_i a_i b_i).

Binds igraph_joint_type_distribution.

Time complexity: O(|E|).

Errors

ErrorKind::InvalidValue if the weight vector or a type vector has the wrong length, or a type vector contains negative values (checked on the Rust side for to_types too, which igraph 1.0.0 and 1.0.1 themselves forget to validate).

Examples

use igraph::prelude::*;

// igraph's unit test: a small undirected multigraph with loops and 3 types.
let g = Graph::from_flat_edges(
    &[3, 0, 0, 3, 0, 2, 3, 1, 5, 5, 4, 2, 1, 1, 1, 1, 0, 1, 5, 1], 6, false)?;
let m = g.joint_type_distribution(None, &[0, 0, 1, 1, 2, 2], None, false, false)?;
assert_eq!(m.to_rows(), vec![
    vec![6.0, 4.0, 1.0],
    vec![4.0, 0.0, 1.0],
    vec![1.0, 1.0, 2.0],
]);

Trait Implementations

impl AsRef<igraph_t> for Graph

A graph is trivially a reference to itself: this lets functions taking several graphs, like layout_merge_dla, accept collections of graphs (Vec<Graph>, &[Graph]) as well as of references (&[&Graph]).

fn as_ref(&self) -> &Graph

Converts this type into a shared reference of the (usually inferred) input type.