Research Interests
Direct Links
Relevant Links

 

Tutorial 01

The following tutorial of the Complex Networks Package generates a random scale-free graph and performs some basic network analysis of it. The script can be downloaded from here.

Contents

  • Generate the network:

    We first use the mexGraphCreateRandomGraph function to construct a 10000-nodes directed network with scale-free degree distribution of α=-2.2.

  • Some basic statistics:

    Here we extract some very basic graph statistics, such as average node degree, reciprocity (fraction of undirectional links), and average clustering coefficient.

  • Node Degree Distribution:

    Node degree distribution is perhaps the most insightful property of complex networks. It's usually one of the first properties one would inspect. Here we compute and plot the node degree distribution which turns out to be a power law (naturally, since that's how the network was initially created).

  • Clustering Coefficient Distribution

    High clustering is another property of most real-world scale-free networks . In this section we show how it is computed and plotted. No surprises here. The algorithm which generated the examined network took care of the node degree distribution only. So the clustering coefficient is close to 0.

  • Clustering Coefficient Dependence on Degree

    Does clustering coefficient of a node depends on it degree? Here we plot average clustering coefficient of nodes grouped by their degree.

  • Components

    Next, we find all strongly connected components. Strongly connected component is such a set of nodes that there exists a directed path between any two nodes in the set. Strongly connected components differ from weakly connected components (where the path may be ubderected) only in directed graphs. In undirected ones, the two kinds of components are equivalent.

  • Remove the most connected nodes (with highest outgoing degree)

    Finally we test the network for its resiliance to node removal. How fast would the network fall apart as its nodes are removed? We perform two types of attacks: attack targeted at the most highly connected nodes and attack targeting random nodes. In each case, we measure percolation threshold and plot system desintegration process as it falls apart.

Generate the network:

NumberOfNodes = 10000; % Number of nodes
Alpha = -2.2;   % Alpha of the scale-free graph
%define node degree distribution:
XAxis  = unique(round(logspace(0,log10(NumberOfNodes),25)));
YAxis  = unique(round(logspace(0,log10(NumberOfNodes),25))).^(Alpha+1);
% create the graph with the required node degree distribution:
Graph = mexGraphCreateRandomGraph(NumberOfNodes,XAxis,YAxis,1);

Some basic statistics:

%Number of nodes in graph:
disp(sprintf('Number of Nodes: %d',GraphCountNumberOfNodes(Graph)));
%Number of links in graph:
disp(sprintf('Number of Links: %d',GraphCountNumberOfLinks(Graph)));
%Average degree:
Degrees = GraphCountNodesDegree(Graph);
disp(sprintf('Average Node Degree: %2.2f',mean(Degrees(:,2))));
%Find fraction of reciprocal links:
Reciprocal = GraphCountUnderectionality(Graph);
disp(sprintf('Fraction of reciprocal links: %2.2f%%',Reciprocal.DoubleConnectivityFraction*100));
% Clustering coefficient:
CC = mexGraphClusteringCoefficient(Graph);
disp(sprintf('Average Clustering Coefficient: %3.3f%%',CC.C));
Number of Nodes: 10000
Number of Links: 46362
Average Node Degree: 4.64
Fraction of reciprocal links: 3.18%
Average Clustering Coefficient: 0.031%

Node Degree Distribution:

h1 = figure;
% incoming:
[y x] = hist(Degrees(:,2),unique(Degrees(:,2)));
loglog(x,y/sum(y),'*r');
hold on
% outgoing
[y x] = hist(Degrees(:,3),unique(Degrees(:,3)));
loglog(x,y/sum(y),'dg');
% expected distribution:
loglog(XAxis,YAxis/sum(YAxis),':b');

xlabel('k,Degree');
ylabel('P(k)');
title('Node Degree Distribution');
legend({'Incoming','Outgoing','Expected'});

Clustering Coefficient Distribution

h2= figure;
% direct
CCin = mexGraphClusteringCoefficient(Graph,[],'direct');
[y x] = hist(CCin.NodeClusteringCoefficient,linspace(0,1,25));
plot(x(x>0),y(x>0)/sum(y),'*r');
hold on;
% inverse
CCout = mexGraphClusteringCoefficient(Graph,[],'inverse');
[y x] = hist(CCout.NodeClusteringCoefficient,linspace(0,1,25));
plot(x(x>0),y(x>0)/sum(y),'dg')
xlabel('CC, clustering coefficient');
ylabel('P(CC)');
title('Clustering coefficient distribution (CC>0)');
legend({'Direct','Inverse'});

Clustering Coefficient Dependence on Degree

h3 = figure;
% direct
loglog(CCin.k,CCin.Ck,'*r');
hold on;
% inverse
loglog(CCout.k,CCout.Ck,'dg');

xlabel('k, Degree');
ylabel('<CC(k)>, clustering coefficient');
title('Average clustering coefficient as a function of degree');
legend({'Direct','Inverse'});

Components

Remove random nodes until the graph breaks apart:

TempGraph=Graph;
NodesToRemovePerStep =1;
NumbersOfNodes = [];
NumbersOfLinks = [];
NumbersOfComponents = [];
LargestClusterSizes = [];
SecondLargestClusterSizes = [];

RemainingNodes = 1:NumberOfNodes;

while ~isempty(RemainingNodes)
    NodeIndecesToRemove = unique(round(rand(NodesToRemovePerStep,1)*(numel(RemainingNodes)-1))+1);
    NodesToRemove = RemainingNodes(NodeIndecesToRemove);
    RemainingNodes = setdiff(RemainingNodes,NodesToRemove);
    TempGraph = mexGraphNodeRemove(TempGraph,NodesToRemove);
    NumbersOfNodes(end+1) = GraphCountNumberOfNodes(TempGraph);
    NumbersOfLinks(end+1) = GraphCountNumberOfLinks(TempGraph);
    if NumbersOfLinks(end)>0
        Components = mexGraphConnectedComponents(TempGraph);
        NumbersOfComponents(end+1) = numel(Components);
        ComponentsSizes = sort(cellfun('length',Components),'descend');
        if ~isempty(ComponentsSizes)
            LargestClusterSizes(end+1) = ComponentsSizes(1);
        else
            LargestClusterSizes(end+1) = 0;
        end
        if numel(ComponentsSizes)>1
            SecondLargestClusterSizes(end+1) = ComponentsSizes(2);
        else
            SecondLargestClusterSizes(end+1) = 0;
        end
    else
        NumbersOfComponents(end+1) = 0;
        LargestClusterSizes(end+1) = 0;
        SecondLargestClusterSizes(end+1) = 0;
    end
end
h4 = figure;
plot(NumbersOfComponents,'r');
hold on;
h5 = figure;
plot(NumbersOfNodes,'r');
hold on;
h6 = figure;
plot(NumbersOfLinks,'r');
hold on;
h7 = figure;
plot(SecondLargestClusterSizes,'r');
hold on;
h8=figure;
plot(LargestClusterSizes,'r');
hold on;

Remove most connected nodes (with highest outgoing degree)

TempGraph=Graph;
NodesToRemovePerStep =1;
NumbersOfNodes = [];
NumbersOfLinks = [];
NumbersOfComponents = [];
LargestClusterSizes = [];
SecondLargestClusterSizes = [];

RemainingNodes = 1:NumberOfNodes;

while ~isempty(TempGraph.Data)
    Degrees = GraphCountNodesDegree(TempGraph);
    [OutDegrees SortOrder]=sort( Degrees(:,3),'descend');
    NodesToRemove = Degrees(SortOrder(1:min([numel(SortOrder) NodesToRemovePerStep])));
    TempGraph = mexGraphNodeRemove(TempGraph,NodesToRemove);
    NumbersOfNodes(end+1) = GraphCountNumberOfNodes(TempGraph);
    NumbersOfLinks(end+1) = GraphCountNumberOfLinks(TempGraph);
    if NumbersOfLinks(end)>0
        Components = mexGraphConnectedComponents(TempGraph);
        NumbersOfComponents(end+1) = numel(Components);
        ComponentsSizes = sort(cellfun('length',Components),'descend');
        if ~isempty(ComponentsSizes)
            LargestClusterSizes(end+1) = ComponentsSizes(1);
        else
            LargestClusterSizes(end+1) = 0;
        end
        if numel(ComponentsSizes)>1
            SecondLargestClusterSizes(end+1) = ComponentsSizes(2);
        else
            SecondLargestClusterSizes(end+1) = 0;
        end
    else
        NumbersOfComponents(end+1) = 0;
        LargestClusterSizes(end+1) = 0;
        SecondLargestClusterSizes(end+1) = 0;
    end
end
figure(h4)
plot(NumbersOfComponents,'g');
xlabel('Step');
ylabel('Number of components');
legend({'Random','Targeted'});
figure(h5)
plot(NumbersOfNodes,'g');
xlabel('Step');
ylabel('Number of Nodes');
legend({'Random','Targeted'});
figure(h6)
plot(NumbersOfLinks,'g');
xlabel('Step');
ylabel('Number of Links');
legend({'Random','Targeted'});
figure(h7);
plot(SecondLargestClusterSizes,'g');
xlabel('Step');
ylabel('Cluster Size');
title('Size of SECOND largest cluster');
legend({'Random','Targeted'});
figure(h8);
plot(LargestClusterSizes,'g');
xlabel('Step');
ylabel('Cluster Size');
title('Size of largest cluster');
legend({'Random','Targeted'});

A large number of clusters emerges around the phase transition

Note the peak of the second-largest cluster suggesting phase transition.