## 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.