Random adjacency matrix with variation on number of edges per node

Question

The following function returns a randomly generated adjacency matrix of size nxn, representing a graph.

import random

def random_adjacency_matrix(n):   
    matrix = [[random.randint(0, 1) for i in range(n)] for j in range(n)]

    # No vertex connects to itself
    for i in range(n):
        matrix[i][i] = 0

    # If i is connected to j, j is connected to i
    for i in range(n):
        for j in range(n):
            matrix[j][i] = matrix[i][j]

    return matrix

It is a very naive solution, and I'd like it to satisfy two additional requirements.

1. The graph the matrix represents must be fully connected, in other words there must not be any nodes that can't be reached from any other node in some number of steps.

2. Each node has a number of edges. Right now it's totally random, and thus fairly uniform how many edges a node has, and when n is large the average number of edges tends to be large too for all graphs. I would like the average number of edges per node to vary more, independent of the size of the graph, so that some graphs have very few connections and others have a lot.

Edit: Using the networkx package, this seems to be what I want, only with point 1 above also satisfied:

import networkx, random
G = networkx.binomial_graph(50, random.random()) # 50 nodes, random probability of an edge

Answer 1

First, let met recommend the networkx graph library. It's very easy to use and has a nice toolbox of algorithms already included. For instance, you can easily test a graph for connectivity or ask for the set of connected components in the graph.

Second, there are a variety of named statstical distributions that are canon. If you could find the one you're thinking of, that would be helpful to both you and anyone that's offering to help. From the rough description that you've given, it sounds like you might be looking for a power-law distribution (aka "long tail" distribution, see also "scale free network"). You see these kinds of distributions a lot in (e.g.) social networks, in which case there are relatively few VERY highly connected nodes (i.e. the popular ones), and then many, many nodes with very low connectivity. Between the few highly connected, and the many sparsely connected, there is a sort of exponential decay in the middle. This seems to be THE paper that describes randomly generated social networks: Random Graph Models of Social Networks.

Given networkx and the appropriate statistical distribution, you should be able to build the graph of your dreams. Good luck with your project, and happy coding.

Answer 2

There is not enough information given to fully specify the type of graph that you want. Nevertheless, since graphs are usually abstractions of some physical structure, a common request for a random graph is one that is scale-free. These graphs have the property that the degree distribution follows a power law asymptotically. Population dynamics, Facebook friends, citation networks and internet traffic all have a power law dependence over some domain. The cannonical method for generating scale-free networks is the Barabási–Albert method. Reproduced below (from wikipedia) is an animation of the creation of such a network. It is guaranteed to be connected for any N and generalizations allow you to set the connectivity.

networkx can generate these random graphs with ease:

import networkx

node_number = 20
initial_nodes = 2
G = networkx.barabasi_albert_graph(node_number, initial_nodes)

Answer 3

Problem 1:

First create a random spaning tree which connects all the nodes together and then add other edges.

Problem 2:

Create a list of all (i,j) for 1 ≤ i < j ≤ n, shuffle the list and take the first k edges. Your graph will then have n vertices and k±n edges.

Answer 4

(1) This one is easy - just create a tree first, and only after the connectivity is assured - start adding more edges.
That can be done easily, by iteratively increasing a set of connected vertices.
Pseudo code:

source <- select random vertex
set <- {source}
while set != V:
   chose a random vertex v from set, and u from V\set
   add (v,u),(u,v) as an edge
   add u to set

(2)
I'd use normal distribution to chose the number of edges per node. Each node will get a different random variable - and thus will have different number of nodes.

• I think it is a good approach since things tend to be normally distributed in real life (due to central limit theorem).
• You can control the connectivity by modifying the mean and variance of the random variables which are used to determine the number of edges per vertex.
• You could also use any other distribution to chose the number of edges per node, but I believe normal distribution fits best.