Contents
- Generate the network:
In this section, we use mexGraphCreateRandomGraph function to construct a 10000-nodes directed network with scale-free degree distribution of α=-2.2.
- Some basic statistics:
Here I show how to extract some very basic statistics from the graph. This includes Average Node Degree, Reciprocity (fraction of undirectional links), and Average Clustering Coefficient.
- Node Degree Distribution:
The most famous property of complex networks is their remarkable degree distribution. It is usually the first property one would check. Here we compute and plot the node degree distribution which proves to be a power law (naturally since that's how the network was initially created).
- Clustering Coefficient Distribution
Another remarkable property of most real-world scale-free networks is the high clustering coefficient of its nodes. 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. Consequently, the obtained clustering coefficient is close to 0.
- Clustering Coefficient Dependence of Degree
This section shows how various measured quantities can be examined to expose some extra information about the system. In this case, we plot average clustering coefficient of nodes grouped by their degree.
- Components
Next, we find all strongly connected components. Each strongly connected component is a set of nodes each of which is reachable from any other. Strongly connected components are only meaningful in directed graphs. In undirected ones, they are equivalent to regular connected components.
- remove most connected nodes (with highest outgoing degree)
Finally I perform two kinds of attacks on the network : attack targeted at the most highly connected nodes and randomly targeted one. In each case, we measure percolation threshold and plot system desintegration process as it's being broken 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 node 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'});
Emergence of a large number of clusters occures around phase transition
Notice the peak of the second-largest cluster marking phase transition.
