Random Graph Generators (4) 

Construct a pseudorandom lobster graph:

In[7]:=

Out[7]=

Create a pseudorandom bipartite graph from two given degree sequences:

In[8]:=

Out[8]=

In[9]:=

Out[9]=

In[10]:=

Out[10]=

Generate a random binomial bipartite graph (a bipartite Erdős-Rényi graph):

In[11]:=

Out[11]=

In[12]:=

Out[12]=

In[13]:=

Out[13]=

Generate a random graph using the built-in Wolfram Language function:

In[14]:=

Out[14]=

In[15]:=

Out[15]=

Construct an artificial Lancichinetti–Fortunato–Radicchi benchmark network resembling real-world networks:

In[16]:=

Out[16]=

Algorithms (5) 

Find trophic levels of a food web:

In[17]:=

Out[17]=

In[18]:=

Out[18]=

Analyze the Human Disease Network using the current-flow betweenness centrality and find vertices that lay on many paths, not necessarily on many shortest paths:

Select the first connected graph in indicating the common genetic origin of diseases in the Human Disease Network:

In[19]:=

Out[19]=

Compute the current-flow betweenness centrality:

In[20]:=

Out[20]=

In[21]:=

Out[21]=

For comparison, compute the shortest-path betweenness centrality:

In[22]:=

Out[22]=

The two measures are very highly (but not perfectly) correlated:

In[23]:=

Out[23]=

In[24]:=

Out[24]=

Pick vertices for which the current-flow betweenness centrality is more than 10 times higher than the shortest-path betweenness centrality. These would be missed by the shortest-path-based methods as mutations do not necessarily follow the shortest paths:

In[25]:=

Out[25]=

Highlight the missed vertices:

In[26]:=

Out[26]=

Analyze the global characteristics of a random, scale-free and clusterized graphs, using the second order centrality that provides graph signatures:

Create e a random graph:

In[27]:=

In[28]:=

In[29]:=

Out[29]=

A scale-free graph:

In[30]:=

Out[30]=

And a clusterized, barbell-type graph constructed from two random graphs joined by an edge:

In[31]:=

Out[31]=

Compute second order centralities:

In[32]:=

The random graph exhibits the lowest values of second order centrality, consistent with the expected low diameter and low clustering coefficient of random graphs. Then follows the scale-free graph showing higher centrality values due to hubs being part of many shortest paths, while most of other vertices having a far inferior global importance. Finally, the clusterized graph shows a distribution with values about three times larger than ones of a single random graph due to the obvious difficulty of the random walk progression in the structure:

In[33]:=

Out[33]=

Demonstrate a percolation transition in the average distance between nodes in the largest cluster of the internet at the Autonomous System (AS) level:

In[34]:=

Out[34]=

Compute k-crusts for the first several values of k:

In[35]:=

In[36]:=

The size of the crust, that is, the total number of nodes that belong to the crust:

In[37]:=

Out[37]=

The mean distance between nodes in the largest cluster of each crust:

In[38]:=

Out[38]=

The mean distance peaks indicating the percolation transition:

In[39]:=

Out[39]=

Analyze the structure of a power grid network:

In[40]:=

Out[40]=

The exponential decay of the power grid's onion spectrum is a signature of its tree-like structure, where most loops are short and link nearby nodes:

In[41]:=

Out[41]=