MATLAB Examples

(3) Graph Analysis and Metrics

Contents

Intro

Created by Brighton Ancelin

This toolbox has four main objectives:

  1. Help the user import a graph from a file or matrix into MATLAB as a graph object
  2. Help the user perform common operations and alterations on graph objects
  3. Provide tools for basic analysis of graph objects and calculation of key metrics
  4. Provide a variety of different visualization means for graph objects, both time-varying and time-invariant

In this page, we will discuss how to generate a graph metrics struct.

All-in-One Metrics Struct

A metrics struct contains many different fields of data about a graph. A brief overview of each field can be seen by using the MATLAB command: help getGraphMetrics

There are two main functions associated with graph metrics fields: getGraphMetrics and exportMetricsFile. The prior can be used to obtain a metrics struct, and the latter can be used to export said metric data into a text file. The latter function will call the prior internally and return the struct, so there's seldom a reason to call the two in succession. An example of proper usage is as follows:

metrics = exportMetricsFile(graph([1,2,3],[2,3,1]),'Title of Graph','filename');
help getGraphMetrics;
  $Author Brighton Ancelin
  Returns a structure of various graph metrics.
 
  INPUT:
 	graphObj: Graph object to be analyzed
 
  OUTPUT:
    metrics: Structure with metrics data. Fields:
 		isDirected: true if graph is directed, false if graph is undirected
 		isFullyConn: true if graph is fully, strongly connected.
 			See also:
 				https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph
 				https://en.wikipedia.org/wiki/Strongly_connected_component
 		distances: NxN (N is the number of nodes) matrix where
 			distances(i,j) represents the shortest path distance between 
 			node i and node j. distances(i,i) will always equal 0,
 			regardless of self-edges.
 			See also:
 				https://en.wikipedia.org/wiki/Shortest_path_problem
 		nodeCt: Integer number of nodes in the graph.
 		edgeCt: Integer number of edges in the graph.
 		avgPathLength: Average of all shortest paths between distinct nodes
 			in the graph.
 		diameter: Maximum shortest path length in the graph, i.e. maximum 
 			value of the aforesaid 'distances' field after matrix 
 			linearization.
 		clusterings: Column vector of local clustering coefficients.
 			clusterings(n) will return the local clustering coefficient of
 			the nth node. Nodes with degree 1 or less (i.e. 1 or fewer 
 			neighbors) are incapable of forming triangles and are given a
 			default clustering coefficient of 0.
 			See also:
 				https://en.wikipedia.org/wiki/Clustering_coefficient#Local_clustering_coefficient
 				http://www.stevenstrogatz.com/articles/collective-dynamics-of-small-world-networks-pdf
 		avgClustering: Average of all local clustering coefficients as
 			defined above.
 		maxEigenvalue: Maximum eigenvalue of the adjacency matrix. By the
 			Perron-Frobenius Theorem, this eigenvalue has an associated
 			eigenvector whose entries are all nonnegative (for undirected 
 			graphs). This is useful for centrality measurements.
 			See also:
 				https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem
 		eigenCentralities: Eigenvector associated with the maxEigenvalue
 			referenced above. eigenCentralities(n) will return the 
 			eigencentrality of the nth node.
 			See also:
 				https://en.wikipedia.org/wiki/Eigenvector_centrality
 		degrees: Column vector of degree values. degrees(n) will return the
 			degree of the nth node.
 			See also:
 				https://en.wikipedia.org/wiki/Degree_(graph_theory)
 		degreeCentralities: Column vector of degree centralities, defined
 			as the degree of each node divided by the maximum degree that
 			node could have. degreeCentralities(n) will return the degree 
 			centrality of the nth node.
 			See also:
 				https://en.wikipedia.org/wiki/Centrality#Degree_centrality
 		closenessCentralities: Column vector of closeness centralities,
 			defined as the reciprocal of the average of all shortest paths 
 			originating from a given node. closenessCentralities(n) will 
 			return the closeness centrality of the nth node.
 			See also:
 				https://en.wikipedia.org/wiki/Centrality#Closeness_centrality
 		distanceDistribution: A table of distance distribution data.
 			The 'Distance' vector contains integer values that represent
 			the shortest path lengths. The 'QuantityOfNodePairs' vector
 			contains corresponding quantities of node pairs that have the
 			associated shortest path between them.
 			See also:
 				http://konect.uni-koblenz.de/plots/distance_distribution_plot
 		assortativityByNode: Column vector of assortativity data.
 			assortativityByNode(n) will return the average degree of all
 			neighbors of the nth node.
 			See also:
 				https://en.wikipedia.org/wiki/Assortativity#Neighbor_connectivity
 		assortativityByDegree: Column vector of assortativity data.
 			assortativityByDegree(n) will return the average of the vector
 			assortativityByNode(arr) where arr contains the node indices of
 			all nodes in the graph of degree n.
 			See also:
 				https://en.wikipedia.org/wiki/Assortativity#Neighbor_connectivity
 
  GRAPH REQUIREMENTS:
 	- Unweighted