1
$\begingroup$

In the definition of a network, are we only considering connected graphs ?

Because I keep encountering definitions that don't assume explicitly that we deal with connected graphs, but which would be very counter-intuitive if they would also apply for disconnected graphs (almost everywhere one is advised to think of a network - the mathematical object - as a network of pipes transporting some fluid; if disconnected graphs come into play this metaphor of pipes transporting something fails!).

  • 0
    @resu: ah, it looks like the term I'm slightly more familiar with is _flow_ $n$etwork: http://en.wikipedia.org/wiki/Flow_network Anyway, I know it's hard to tell whether a definition is standard or not, but when in doubt please include all of the definitions you're using.2011-07-23

3 Answers 3

1

I don't see how the metaphor fails if the graph is disconnected. Your pipe system is just broken (or perhaps under construction), and no flow is possible. A broken system of pipes is still a system of pipes.

0

It is possible that the author had a sensor network in mind. These usually have sensors (sources) and a sink that fuses the sensor readings. The capacity can also be defined.

These networks may or may not be connected. Obviously it helps if there is always a path from all sources to the sink. If the path momentarily disappears, the sources may store their readings until a route is re-established, etc.

0

Outside of flow networks (which are precisely defined)...

What is the right way to think of a network?

There isn't one right way. What a "network" is is context dependent. Authors often do not give a precise definition of a network, instead opting for a more encompassing intuitive definition of "network".

Should one think of a network as a connected graph ?

  • In real-world contexts, a network might not even be considered a graph.

    For example, in a biological neural network neuronal connections are made via an axon to other neurons. A single axon may connect to many other neurons (and have many connections to each of them). This is an advantage for e.g. coordinating movement.

    It's not obvious how to interpret the network as a graph (and whether or not a graph is the best data structure to use). E.g. if we represent a single axon with multiple edges, then the graph does not capture the property that if we cut that single axon, then we cut a whole bunch of edges.

  • In real-world contexts, for a network that is considered a graph (which may or may not be directed), it may or may not be important that the graph is connected (either weakly or strongly). E.g. in my area of research, network motifs, it can be largely ignored (it's not relevant to the problems we're trying to solve).

    In cases where connectivity is important (e.g. computer networks), the distinction between connected and disconnected networks is an important consideration. In other studies, a largest component (or giant component) may be instead studied.