0

enter image description hereIn a game, we have a universe described as a strongly-connected graph full of sectors and edges. Occasionally there are small pockets, players call them 'bubbles', where a small group of nodes all access the rest of the network through a single node. In the graph below, sectors 769, 195, 733, 918, and 451 are all only reachable via node 855. If you can guard 855 effectively, then those other sectors are safe. Other nodes on the chart have more edges (purple lines) and aren't 'bubbles' in the player nomenclature.

In a 1000 or 5000-node network, it's not easy to find these sorts of sub-structures. But I suspect this idea is described in graph theory somehow, and so probably is searchable for in networkx.

Could anyone suggested a graph-theory approach to systematically find structures like this? To be clear the graph is a directed graph but almost all edges end up being bi-directional in practice. Edges are unweighted.

user3556757
  • 3,469
  • 4
  • 30
  • 70
  • 1
    So what you've identified is a "cut vertex" - a node that when deleted disconnects the graph. Take a look at https://stackoverflow.com/questions/15873153/explanation-of-algorithm-for-finding-articulation-points-or-cut-vertices-of-a-gr – Joel May 02 '19 at 00:25
  • @joel this was what i needed... nx.articulation_points. Thanks for the tip. – user3556757 May 03 '19 at 05:55

1 Answers1

0

Graph theory has no definitions for your "bubbles", but has the similar definition - bridges. Bridge is the edge, which removal increases the number of connected components. As you can see, it is exactly what you need. networkx has a bunch of algorithms to find bridges. Curiously enough, it is called bridges :)

Example:

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    (1,2),(1,3),(2,3),
    (1,4),(4,5),(5,6),
    (6,7),(7,4)
])
nx.draw(G)
list(nx.bridges(G))

[(1, 4)]

enter image description here

vurmux
  • 9,420
  • 3
  • 25
  • 45
  • thanks, but I think the concept of 'articulation points' which is what joel mentioned in the comments above is pretty much excactly what I was looking for. Find the articulation points and then look at the size of the resultant connected components. – user3556757 May 13 '19 at 02:39