Build adjacency matrix from a list of nodes by avoiding for loops

This question is related strongly with my investigations discussed before 10 days, so I'll post a summary of the most important discoveries here.

• Storing communities as lists of unbalanced lengths forces to use iterations or concatenations which is not efficient. Instead you could use a single array and counts like so:

      flow = [0,3,4,2,1,0,3,5]
      counts = [3,3,2]
  

• A faster way for single combinations is a np.triu_indices method instead of itertools.combinations:

  def combs(t):
       x, y = np.triu_indices(len(t), 1)
       return np.transpose([t[x], t[y]])
  

  It is pointed out in my solution that you are looking how to avoid both concatenation and list comprehension in:

  np.concatenate([combs(n) for n in list_indices])
  

  or, alternatively (from itertools import*):

  np.array(list(chain(*[combinations(n,2) for n in list_indices])))
  

• I found a couple ways to vectorise it depending on your input:

  def repeat_blocks(a, sizes, repeats):
      #Thanks @Divakar: https://stackoverflow.com/a/51156138/3044825
      r1 = np.repeat(np.arange(len(sizes)), repeats)
      N = (sizes*repeats).sum() # or np.dot(sizes, repeats)
      id_ar = np.ones(N, dtype=int)
      id_ar[0] = 0
      insert_index = sizes[r1[:-1]].cumsum()
      insert_val = (1-sizes)[r1[:-1]]
      insert_val[r1[1:] != r1[:-1]] = 1
      id_ar[insert_index] = insert_val
      out = a[id_ar.cumsum()] 
      return out
  
  def concat_combs1(flow, counts):
      #way 1 based on repetition of blocks of consecutive items
      col1 = repeat_blocks(flow, counts, counts)
      col2 = np.repeat(flow, np.repeat(counts, counts))
      return np.transpose([col1, col2])[col1 < col2]
  
  def concat_combs2(targets, counts):
      #way 2 based on repetition of blocks dissociated from each other
      counts = list(map(len, targets))
      col1 = np.concatenate(np.repeat(targets, counts, axis=0))
      col2 = np.repeat(np.concatenate(targets), np.repeat(counts, counts))
      return np.transpose([col1, col2])[col1 < col2]
  

  Test:

  list_indices = [np.array([0,3,4]), np.array([2,1,0]), np.array([3,5])]
  flow = np.array([0,3,4,2,1,0,3,5])
  counts = np.array([3, 3, 2])
  # Usage:
  np.concatenate([combs(n) for n in list_indices])
  concat_combs1(flow, counts)
  concat_combs2(list_indices)
  

  Output:

  array([[0, 3],
         [0, 4],
         [3, 4],
         [1, 2],
         [0, 2],
         [0, 1],
         [3, 5]])
  

Conclusion

Four methods has been perfploted on igraph.Graph.Barabasi(n = x, m = 3) including itertools.combinations and np.triu_indices. Each vertex of this graph has 3 neighbours in average. In conclusion, connection of repeated consecutive blocks works the best. Concatenation of numpy arrays is slower than chaining combinations for this time because very large number of small lists is being concatenated.

Final solution

In order to construct a matrix of incidence in a fastest way, you need to apply a small variation of concat_combs1 method:

flow = np.array([0,3,4,2,1,0,3,5])
counts = np.array([3,3,2])
results = np.zeros((np.max(flow)+1, np.max(flow)+1), dtype=int)
col1 = repeat_blocks(flow, counts, counts)
col2 = np.repeat(flow, np.repeat(counts, counts))
results[col1, col2] = 1
np.fill_diagonal(results, 0)

Output

[[0 1 1 1 1 0]
 [1 0 1 0 0 0]
 [1 1 0 0 0 0]
 [1 0 0 0 1 1]
 [1 0 0 1 0 0]
 [0 0 0 1 0 0]]