given V nodes and E connections as parameters, how do I generate random directed fully-!connected! adjacent probability matrix, where all the connections weights fanning out of a node sum to 1.

The idea is after I pick random starting node to do a random walk according to the probabilities thus generating similar-random-structured sequences.

Although I prefer adj-matrix, graph is OK too.

Of course the fan-out connections can be one or many. Loops are OK just not with itself.

I can do the walk using np.random.choice(nodes,prob)

Now that Jerome mention it it seem I was mistaken .. I dont want fully-coonnected BUT a closed-loop where there are no islands of sub-graphs i.e. all nodes are accessible via others.

Sorry I dont know how is this type of graph called ?

here is my complex solution ;(

def gen_adjmx(self):
    passx = 1
    c = 0 #connections so far
    #until enough conns are generated
    while c < self.nconns :
        #loop the rows
        for sym in range(self.nsyms):
            if c >= self.nconns : break
            
            if passx == 1 : #guarantees at least one connection
                self.adj[sym, randint(self.nsyms) ] = randint(100)
            else:
                if randint(2) == 1 :    #maybe a conn ?
                    col = randint(self.nsyms)
                    #already exists
                    if self.adj[sym, col] > 0 : continue 

                    self.adj[sym, col ] = randint(100)
                    c  = 1

            passx  = 1      

    self.adj /= self.adj.sum(axis=0)

CodePudding user response：

You can simply create a random matrix and normalize the rows so that the sum is 1:

v = np.random.rand(n, n)
v /= v.sum(axis=1)

CodePudding user response：

You mentioned that you want a graph which doesn't have any islands. I guess what you mean is that the adjacency matrix should be irreducible, i.e. the associated graph doesn't have any disconnected components.

One way to generate a random graph with the required property is to generate a random graph and then see if it has the property; throw it out and try again if it doesn't, otherwise keep it.

Here's a sketch of a solution with that in mind.

(1) generate a matrix n_vertices by n_vertices, which contains n_edges elements which are 1, and the rest are 0. This is a random adjacency matrix.

(2) test the adjacency matrix to see if it's irreducible. If so, keep it, otherwise go back to step 1.

I'm sure you can implement that in Python. I tried a proof of concept in Maxima (https://maxima.sourceforge.io), since it's convenient in some ways. There are probably ways to go about it which directly construct an irreducible matrix.

I implemented the irreducibility test for a matrix A as whether sum(A^^k, k, 0, n) has any 0 elements, according to: https://math.stackexchange.com/a/1703650 That test becomes more and more expensive as the number of vertices grows; and as the ratio of edges to vertices decreases, it increases the probability that you'll have to repeat steps 1 and 2. Whether that's tolerable for you depends on the typical number of vertices and edges you're working with.

random_irreducible (n_vertices, n_edges) :=
    block ([A, n: 1],
           while not irreducible (A: random_adjacency (n_vertices, n_edges))
               do n: n   1,
           [A, n]);

random_adjacency (n_vertices, n_edges) :=
    block([list_01, list_01_permuted, get_element],
          list_01: append (makelist (1, n_edges),  makelist (0, n_vertices^2 - n_edges)),
          list_01_permuted: random_permutation (list_01),
          get_element: lambda ([i, j], list_01_permuted[1   (i - 1)   (j - 1)*n_vertices]),
          genmatrix (get_element, n_vertices, n_vertices));

irreducible (A) :=
    is (member (0, flatten (args (sum (A^^k, k, 0, length(A))))) = false);

A couple of things, one is I left out the part about normalizing edge weights so they sum to 1. I guess you'll have to put in that part to get a transition matrix and not just an adjacency matrix. The other is that I didn't prevent elements on the diagonal, i.e., you can stay on a vertex instead of always going to another one. If that's important, you'll have to deal with that too.