Measure for presence of several poorly interconnected components in undirected graph

60 Views Asked by At

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That is, a measure that does not just measure clustering or bottleneckedness but would be actually able to distinguish a network like this (I believe, you might refer to it as a complex network but I'm not sure the term is quite able to capture it) from a regular network (say, a ring or a double ring something similar). (By double ring I mean something like the network A here, i.e. the regular network with which Watts and Strogatz started when creating their small world model.)

A little more explanation: Measures that might go into the right direction include ...

When I try to explain verbally what kind of measure I want, I am tempted to use the word 'clustering' because what I essentially want to know is whether a network contains distinct, well, 'clusters'. Formal clustering measures, however, measure just the share of the closed triads in total triads (locally or globally) and similar things (or similar values). A double ring, for instance has a substantial local and global clustering (clustering coefficient of 0.5) but is perfectly regular.

The same seems to apply to bottleneckedness. A complex network like the one I referred to above has certainly bottlenecks. But measures of bottleneckedness (specifically, the Cheeger constant) do not distinguish between 'isolated bottlenecks' or 'regular bottlenecks'. Essentially they perceive regular networks (one dimensional regular networks at the least, rings or double rings) as networks of bottlenecks.

Finally there is an extensive literature on segregation measures (see dx.doi.org/10.1016/j.socnet.2014.04.001 ) but this requires pre-defined attributes or groups.

And still a little more explanation: Why would it be important to be able to distinguish such networks

It would have consequences for epidemics (clusters get infected quickly, but it takes time for the pathogen to spread beyond the cluster; time in which the cluster may develop immunity) and 'quasi-epidemics' (spread of behavior, of network technologies, ...).

1

There are 1 best solutions below

0
On BEST ANSWER

Search Betweeness Centrality. This measures how vital a node is in getting information across to other nodes. If the network has clusters with few links between them, the vertices that join two clusters will have very high betweeness centrality. If the network is more connected, the betweeness centrality of everyone will be very close.