Although a bit mathematically dense, “A Survey of Gossiping and Broadcasting in Communication Networks” is an interesting study on communication within networks. The article, described at http://www3.interscience.wiley.com/cgi-bin/fulltext/113394325/PDFSTART, breaks down these communication problems into two general categories: “gossip” and “broadcasting.” For both types, each person in a network is represented by a node and the available lines of communication are represented as edges connecting the nodes. The study examines (from a mostly theoretical perspective) the minimal amounts of time or minimal number of rounds required for information to pass from one node to every other node based on various rules for communication. It also examines the most efficient network structures to distribute information for a given number of nodes. In the gossip problems, every node is assigned some piece of information which they then have to distribute to every other node in the network. For broadcasting problems, one node starts with information that must then be passed to every other possible node.

The study gives a number of variations, and notes how they alter the results. The study, for example, discusses limiting communication in such a way that information cannot be passed back to nodes which already know this information. It also discusses the possibility of allowing any given node to communicate with more than one other node on a given turn. Other variations include trying to simulate communication on a computer network or allowing for different types of edges between various nodes representing communication by whispering or shouting (more nodes can be reached simultaneously through the “shouting” method).

Although I will not get into the mathematical details of the paper, there were some interesting results. Perhaps one of the most unusual has to do with what is known as a minimum broadcast graph. For any given number of nodes, one can draw a number of different graphs by altering the arrangement of edges. On certain graphs, broadcasting information to all nodes takes less time than on others, and for any given number of nodes, one is able to calculate the minimum possible time to fully distribute information. A minimum broadcast graph is a graph that, for its number of nodes, achieves the minimum possible time with the minimum possible number of edges. Intuitively, one might think that as the number of nodes increases, one would need an ever increasing number of edges to efficiently transmit information. This turns out to be false, however, as adding an addition node to a graph of eight or 16 nodes will actually reduce the number of edges required for the minimum broadcast network.

The article gives little information regarding the specific path information takes through any given network arrangement, but it would be interesting to see whether it corresponds to the strength of weak ties discussed in lecture. For larger, more complex networks, it would seem that local bridges would provide a much more efficient route for the transfer of information between distant portions of the network. It would therefore seem likely that these edges are used early in the algorithms that attempt to distribute information as efficiently as possible through the network. The article also assumes the networks studied are connected, a concept we discussed in class that requires that all nodes have some path to every other node. This is an obvious requirement for the study, as a disconnected graph would prevent some nodes from accessing the information.