Module mixing 

Clustering, degree correlations and graphicality: transitivity, assortativity, mixing matrices and degree-sequence realizability.

This module binds three igraph headers:

• igraph_transitivity.h — how clustered is a graph? The global transitivity (fraction of closed connected triples), the local clustering coefficient of Watts and Strogatz, its average, Barrat’s weighted variant and the edge clustering coefficient of Radicchi et al.;
• igraph_mixing.h — who connects to whom? Newman’s assortativity coefficients (for numeric values, for categories and for degrees), the joint degree matrix, the joint degree distribution and the mixing matrix of vertex categories;
• igraph_graphicality.h — can a degree sequence be realized? The Erdős–Gallai / Fulkerson–Chen–Anstee / Gale–Ryser tests, extended to graphs with self-loops and/or multi-edges.

Functions that take a graph are methods of Graph; the graphicality tests work on plain degree slices and are free functions.

Rust	C function	Computes
Graph::transitivity_undirected	igraph_transitivity_undirected	global clustering coefficient
Graph::transitivity_local_undirected	igraph_transitivity_local_undirected	local clustering coefficient of vertices
Graph::transitivity_avglocal_undirected	igraph_transitivity_avglocal_undirected	average local clustering coefficient
Graph::transitivity_barrat	igraph_transitivity_barrat	Barrat’s weighted local clustering
Graph::ecc	igraph_ecc	edge clustering coefficient (3- and 4-cycles)
Graph::assortativity	igraph_assortativity	assortativity by numeric vertex values
Graph::assortativity_nominal	igraph_assortativity_nominal	assortativity by vertex categories
Graph::assortativity_degree	igraph_assortativity_degree	degree assortativity
Graph::joint_degree_matrix	igraph_joint_degree_matrix	edge counts between degree classes
Graph::joint_degree_distribution	igraph_joint_degree_distribution	joint degree distribution P_ij
Graph::joint_type_distribution	igraph_joint_type_distribution	mixing matrix of vertex categories
is_graphical	igraph_is_graphical	is a (bi-)degree sequence realizable?
is_bigraphical	igraph_is_bigraphical	is a pair of sequences realizable as a bipartite graph?

Which kinds of edges the graphicality tests may use is described by AllowedEdgeTypes (defined in constants and shared with the games and constructors modules), which also converts from EdgeTypeSw.

All functions of this module are deterministic.

See also

• Triangles themselves: Graph::count_triangles, Graph::count_adjacent_triangles and Graph::list_triangles (the global transitivity is 3 × triangles / connected triples), the triad census and motifs.
• Degree correlations as functions of the degree: the average nearest neighbor degree Graph::avg_nearest_neighbor_degree and Graph::degree_correlation_vector (k_nn(k), derivable from Graph::joint_degree_distribution); vertex strengths for weighted degrees; the rich-club coefficient.
• Categories: the unnormalized nominal assortativity is the modularity of the partition, and community detection (e.g. Graph::community_multilevel) finds partitions with high values.
• Degree sequences: build a graph from a graphical sequence with Graph::realize_degree_sequence / Graph::realize_bipartite_degree_sequence (deterministic) or Graph::degree_sequence_game / Graph::k_regular_game (random); randomize a graph while keeping its degrees with Graph::rewire, the usual null model against which clustering and assortativity are compared.

Example

use igraph::mixing::{is_graphical, AllowedEdgeTypes};
use igraph::prelude::*;

// A "bow tie": two triangles sharing vertex 2.
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)], 5, false)?;

// 2 triangles, 3 * 2 = 6 closed triples out of 10 connected triples.
let t = g.transitivity_undirected(TransitivityMode::Nan)?;
assert!((t - 0.6).abs() < 1e-12);
assert_eq!(g.count_triangles()?, 2.0);

// The hub closes 2 out of the 6 pairs of its neighbors, the others all theirs.
let local = g.transitivity_local_undirected(.., TransitivityMode::Zero)?;
assert!((local[2] - 1.0 / 3.0).abs() < 1e-12);
assert_eq!(local[0], 1.0);

// High-degree hub attached to low-degree vertices: disassortative.
assert!(g.assortativity_degree(false)? < 0.0);

// Its degree sequence is, of course, graphical.
let degrees = g.degree(.., NeighborMode::All, Loops::Twice)?;
assert!(is_graphical(&degrees, None, AllowedEdgeTypes::SIMPLE)?);
// ...while an odd degree sum never is.
assert!(!is_graphical(&[3, 3, 3], None, AllowedEdgeTypes::ALL)?);

// Zachary's karate club: clustered, and its hubs avoid each other.
let karate = Graph::famous("Zachary")?;
let c = karate.transitivity_undirected(TransitivityMode::Nan)?;
assert!((c - 0.2556818).abs() < 1e-6);
assert!((karate.assortativity_degree(false)? + 0.475613).abs() < 1e-6);

Re-exports

pub use crate::constants::AllowedEdgeTypes;

Structs

JointDegreeDistributionOptions

Options of Graph::joint_degree_distribution.

Functions

is_bigraphical

Is there a bipartite graph with the given pair of degree sequences?

is_graphical

Is there a graph with the given degree sequence?