Getting Started

Set a seed for reproducibility

If reproducible results are needed when using indeterminate methods, set MATLAB’s random number generator seed.

rng(1234);

(See the RNG livescript for more on random number generators.)

Getting a graph to work with

There are several methods to get a graph: loading a graph from file (igraph.load), accessing a common graph (igraph.famous), or generating a new graph (igraph.generate, for determinate graphs, or igraph.randgame, for stochastic graphs). Many of the methods for generating graphs have a set of optional arguments to modify the resulting graph. These optionals can be found by viewing help igraph.generate or help igraph.randgame. As an example, the Barabasi Bag method can be used to produce a graph with 15 nodes.

graph = igraph.randgame("BarabasiBag", nNodes = 15)

graph = 
  graph with properties:
    Edges: [14x1 table]
    Nodes: [15x0 table]

Since the random number generator seed was set, the above command will always produce the same graph, otherwise the graph would vary from call-to-call.

Adjacency graph options

By default graphs are represented as a graph or digraph object depending on whether it’s undirected or directed. Any function that returns a graph has the option to use a full or sparse matrix instead of a MATLAB graph and double or logical data type.

graph = igraph.rewire(graph, repr="sparse", dtype="logical")

graph = 
   (2,1)      1
   (5,1)      1
   (6,1)      1
   (9,1)      1
  (14,1)      1
   (7,2)      1
   (8,2)      1
   (6,3)      1
   (7,4)      1
  (15,4)      1
   (7,6)      1
  (11,9)      1
  (13,9)      1
  (12,10)     1

Methods that both accept and return a graph behave different than those that only return a graph. The input graph will be used as a template for the output graph. If a function that returns a graph is passed a graph in a sparse representation, the resulting graph will also be in a sparse representation.

Saving and loading graphs

Once a graph is in memory, it can be saved to a file and then read back later. Either a graph file type or MATLAB’s mat file type can be used. (See help igraph.save and help igraph.load for information about which graph files can be used, Note: there are some file types that can be saved to but cannot be loaded, to prevent challanges in retrieving data make sure you check if the file type can be read.) The save and load functions will try to determine the file type based on the extension, but the format option can be used to explicity request a specific reader/writer.

igraph.save("rewired.txt", graph);
newGraph = igraph.load("rewired.txt", dtype="logical", repr="full");
isequal(graph, newGraph)

ans = 
   1

Notice the new adjacency matrix is a full logical matrix despite a spares matrix being saved. The representation of the data is kept completely separate from the data itself.

Clean up the left behind file.

delete("rewired.txt");

A note about directedness

Graphs represented as plain matrices don’t store any additional metadata, as such, the directedness of the graph is not tracked. Instead, functions that depend on whether the graph is directed or not will use a test (igraph.isdirected), that will try to cleverly determine whether the graph is directed or not. The igraph.isdirected test assumes the graph is undirected if it’s symmetric or triangular. It’s possible that a graph could be directed and fail the test of directedness. It should be unlikely, but in the case of a small graph with few edges or when starting with a symmetric graph that should be treated as directed the default behavior may be undesired. In these cases, the isdirected option should be explicitly set.

Additionally, in the case of undirected graphs, a symmetric graph, lower triangular, and upper triangular are treated as equivalent by the mxIgraph library. Because of this, when reading a graph from file, you may find the graph is the transpose (or half) of what was expected. For consistency and to match igraph functions, when generating or loading an undirected graph, only the lower half of the matrix will be collected.

When using a MATLAB graph or digraph, the directedness is stored and does not need to be guessed (but it can still be overridden with the isdirected option if an undirected graph should be treated as directed).

Plotting

Graphs can be plotted using different layout algorithms.

igraph.plot(graph, "kk");

Or a premade set of points can be provided to the plot method in order to customize the positions or reuse a layout for multiple plots.

layout = igraph.layout(graph, "graphopt");
igraph.plot(graph, layout);

Membership and sizes can also be displayed.

graph = igraph.famous("zachary");
betweenness = igraph.centrality(graph, "betweenness");
membership = igraph.cluster(graph, "infomap");
igraph.plot(graph, "kk", nodeColor=membership, size=betweenness)

When using a MATLAB graph object, the graph class’ methods are also available:

graph.plot()

A simple example: Community detection

Before starting, lets set a random seed and generate a graph based on a predetermined membership vector. Instead of using an igraph graph generation method, we can take advantage of base MATLAB to create our own generator. This will create an adjacency matrix with some number of communities and a constant probability for within community edges and between community edges.

rng(4920);        % Ensure reproducible results.

Define some constants for creating an example graph. The smaller pIn and greater pOut, the harder it will be for the community detection algorithms to reproduce the original structure.

nNodes = 50;
nCommunities = 6;
groundTruth = randi([1 nCommunities], 1, nNodes);
pIn = 0.6;
pOut = 0.2;

To generate the graph, we will use the ground truth as a template. Start with all within community edges existing and no between community edges.

graph = groundTruth == groundTruth';

Now we can randomly remove within community edges with probability (1 - pIn) and randomly add between community edges with probability pOut.

within = graph .* (rand(nNodes, nNodes) < pIn);
between = (1 - graph) .* (rand(nNodes, nNodes) < pOut);
graph = tril(within + between, -1); % -1 removes the diagonal (self-loops).

To visualize the new graph we can plot the graph, coloring it’s nodes with the original community structure. While the Fruchterman-Reingold algorithm should do a good job of separating the communities on it’s own, to give it a little help and to demonstrate costumizing templates, we’ll provide an initial layout which places all members of a given community in a community starting position.

Because the within community edge probability was set low, the graph’s optimal solution may no longer match the ground truth, this would lead to the layout algorithm places vertices far from their original community. To force the algorithm to keep the nodes near the “ground truth” community, the layout’s start temperature and number of iterations were significantly reduced from their defaults.

communityPositions = [randperm(nCommunities); randperm(nCommunities)]';
templateLayout = communityPositions(groundTruth, :);
layout = igraph.layout(graph, "fr", initial=templateLayout, startTemp=0.1, nIterations=15);
igraph.plot(graph, layout, nodeColor=groundTruth, edgeAlpha=0.2);

Trying different community detection algorithms to predict the original community structure

communities.fastgreedy = igraph.cluster(graph, "fastgreedy");
communities.walktrap = igraph.cluster(graph, "walktrap");

Now plot with the previously made layout to visualize the partitions and compare the results to the original ground truth.

igraph.plot(graph, layout, nodeColor=communities.fastgreedy, edgeAlpha=0.2);

igraph.plot(graph, layout, nodeColor=communities.walktrap, edgeAlpha=0.2);

It’s clear from the distribution of colors throughout the graph, the community detection algorithms are not picking up the ground truth community structure. But is this because they are failing or because the graph has been rewired so much the ground truth community structure no longer fits the graph?

Comparing the results

First, how similar are the two estimated partitions?

igraph.compare(communities.fastgreedy, communities.walktrap)

ans = 0.2852

Not very similar. The algorithms do not agree on how to cluster the nodes. By default igraph.compare uses normalized mutual information. See help igraph.compare for the list of available community comparison algorithms.

How similar was each partition to the original partition?

igraph.compare(groundTruth, communities.fastgreedy)

ans = 0.4500

igraph.compare(groundTruth, communities.walktrap)

ans = 0.3175

The partitions also differ significantly from the original ground truth partition, but that was already obvious from the above plots.

How did the two partitions do with respect to the modularity metric?

qTruth = igraph.modularity(graph, groundTruth);
igraph.modularity(graph, communities.fastgreedy) / qTruth

ans = 1.0538

igraph.modularity(graph, communities.walktrap) / qTruth

ans = 1.0064

Based off the membership comparison, we see the three partitions are not too similar yet they provide similar modularity, indicating there isn’t a clear best partition.