Abstract
Connecting all the members of a large group involves many exchanges; think of it as clinking glasses at a social gathering. Allowing second-hand exchanges/clinks where the group splits into subgroups who clink glasses, and then representatives from each subgroup clink with each other – second-hand clinking – can decrease the number of clinks. This paper finds the optimal number of subgroups necessary to minimise the total number of clinks. It also looks at what is optimal if there is third and higher level clinking. Examples are given of such problems arising in parallel computer systems, social media, communication systems, and sports tournaments.
1. Introduction
Social events, such as parties, often promote interpersonal contact by an initial round of mutual glass-clinking. One clink between each individual of a group of means clinks in all, quite feasible in small settings, but impossible in large ( or so).
In Figure 1,
One way to accomplish such contact is by accepting second-hand clinking: split the whole group of into roughly equal size subgroups; promote first-hand clinking within each subgroup. So denotes the number of these first-level subgroups while there are individuals in total. Select a single member of each first-level subgroup to represent that subgroup in another small, representative, subgroup; and let the representatives in the latter group exchange clinks. In this way each individual clinks/connects with each other individual with a much smaller maximum number of clinks, . What is the optimal size of the first-hand subgroups/communities or (where is the largest integer less than or equal to ) so as to minimise the total number of clinks/connections? This is, in effect, designing a small world, a network with a small number of connections between any two individuals. For example one group of people would result in clinks; splitting the people into four communities with three people each results in total connections. This compares with , and . This illustrates the beneficial effect of wise group/subgroup design.
In Figure 2, total connections with four groups of three people each.
Before addressing the above simplistic question, observe that the general situation described represents various operational scenarios involving connections and communications. One example occurs when deciding how to connect central processing units (CPUs) in a parallel processor computer. Is it necessary to connect all units together or can we collect them in clusters and then connect between the representatives of the different clusters?
On a more social level, how many friends should a group on Facebook have so as to be able to spread messages throughout the group? All members of the group are split into subgroups where they make friends with everyone in the subgroup. One from each group then is made the representative for the group and the representatives become friends with each other.
A different situation in which a similar problem occurs is the setting of ATM interchange fees by banks in the same ATM network. Each year, banks meet to set fees for ATM transactions when customers of one bank uses a different bank’s ATM. Meetings to set the fee can be decreased by having groups of banks deciding on their individual interchange fees and then electing a representative to meet with representatives from other groups. Another example occurs in organisations which have local branches, regional groups and a national group. The local group ‘clinks glasses’ by discussing and deciding matters. They elect representatives for the next level who convey the views of the local group and so on upwards. Examples range from church organisations to political parties. Finally it is also the structure of many sporting tournaments where the clinking is when teams play each other and the winner of the group goes up a level to play other winners. So in the end the winner will have ‘beaten’ every other team if only sometimes at second or third hand. We will discuss later the more common variant of this where two representatives – the winner and runner-up of the group go forward to the next level.
2. Optimal two-tier grouping
Divide individuals into subgroups of (approximately) equal size. Each member of each subgroup then connects (‘clinks’) once with each fellow subgroup member. Then a single member representative of each subgroup joins a higher level group and all members of that group connect (‘clink’). What is the (approximate) number, , that minimises the total number of connections? Putting for the total number of connections/clinks as described above,
(1)
Approximate by neglecting the distinction between and and between and :
(2)
(3)
A second differentiation verifies convexity, so the (near) minimising value of the primary subgroup number is
(4)
Although (2) varies from (1) by , the that maximises (1) is very similar to (4) when is less than . Of course the value of is not likely to be an integer that divides the total, , into equal-sized integer-valued subcommunities, so we adjust to whatever of the nearest integers give the minimum value. Numerical exploration for limited (e.g., ) shows that such a procedure gives very nearly the minimum-connection allocation. The approximate optimal size of each of the first-tier communities is
(5)
With the two-stage grouping in place, the total number of connections/clinks, both first and second level, is approximately
(6)
(7)
We take to be the actual minimum using integer numbers in each subgroup. Insistence on direct connections/clinks between all participants results in the number of connections being about ; so by allowing second-level connection (through a representative) to count the system requires a fraction less clinking where
(8)
Table 1 displays the number of clinks required for various subgroups of a total population allowing for the adjustment to get integer values. If only about as many connections are required in the two-level small world as in the one large world case.
3. General recursion
The idea of second-hand clinking can be extended to third-hand and higher tiers/levels of clinking. In this, a representative of a subgroup at a lower level meets representatives of some of the other such subgroups to form a subgroup at the next higher level. If one allows third-level (third-hand) clinking, then define to be the number of first-level subgroups each of or individuals. At the second level there are groups each of or representatives from the lower tier. Finally at the third tier there is one group consisting of members each of which represents one of the second tier subgroups. For example, one possibility for people is as follows: the first tier contains six groups of two people each; the second tier consists of three groups of two people each; and the third tier has one group of three people. This is shown in Figure 3 with three levels of clinking, where first-level clinking is thin lines, second-level clinking is the dotted lines and third level clinking is the thicker lines.
where (6) is substituted into (9) with and replacing and . This gives and ; the form is inferred from (6) and (7). Next differentiate (10) and set the derivative equal to to find optimum numbers of subgroups at the first tier:
(11)
From (4)
(12)
Combining (11) and (10) results in
(13)
Further exploration shows that a power-law recursion holds for more tiers.
Let be the optimal number of individuals in the level subgroup when there are tiers of connection. Let be the minimising total number of connections under the same conditions. A recursive argument on yields
where
(16)
and
The optimal numbers of individuals in each of the other subgroup tiers are
(19)
for .
Applying these results to third-hand clinking gives the results in Table 2. So the approximations for the number of groups works well and three tiers decreases the needed clinking/connections.
4. Two first-level representatives
We mentioned earlier that in sporting tournaments there are often two representatives who are chosen from the first-level groups. Each representative from a group is put in a different group at the next level. Call them Groups A and B. One can then apply normal or higher level clinking to these groups. This ensures that two members of the original group have two ways in which their clinking can occur – one through the representatives in Group A and one through the representatives in Group B. In fact if there is a higher level of clinking with one representative from Group A and one from Group B having a final clink (just like the the ‘final’ of a sporting competition) there would be four ways any two people in the original group have clinked via high order clinking. The first is through the Group A representatives of each person; the second through the Group B representatives of each person clinking and two ways through the Group A representative of one person clinks with the Group B representative of the other through that final higher level clink. The ideal number of first-level groups can be estimated using an adaption of (9). If there are first-level groups and we take to be the number of subsequent higher level clinks involved if there are first-level groups, then instead of the total number of clinks (excluding the final clink between one representative from A and one representative from B) being
(20)
which is a generalisation of (9), it would be
(21)
since there are higher order clinks in Group A and a similar number in Group B. In the simplest case where there is only second-hand clinking, this gives rise to the optimal being . Applying this to the cases with , , and gives Table 3 where the total number of clinks ignores the final single clink.
Of course in sports tournaments the objective is not to minimise the number of matches played but instead play the number of matches required by the broadcasting rights. However, this approach can allow one to look at the tournament structure that provides the requisite number of clinks/matches/connections.
5. Discussion
The focus of this note is on network design to optimise a particular measure of performance. Ours is an architectural study, differing from the great majority of previous works, for example [1, 2]. These aim to describe plausible behavioural dynamics that lead to small-world connections. Behavioural models apparently stem from classical experiments [3]. Our formulations for increasing tiers eventually lead to an optimised Moore graph [4]. Changes in the system performance metric will naturally lead to altered graph configurations. For instance, recognition of link or node unreliability, or congestion at sensor-servers, will demand combined architectural and sensor behavioural dynamic accommodation requiring further study.
Donald P. Gaver
Naval Postgraduate School, Monterey, California
Patricia A. Jacobs
Naval Postgraduate School, Monterey, California
Lyn C. Thomas FIMA
University of Southampton
References
- Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of `small world’ networks, Nature, vol. 393, pp. 330–442.
- Newman, M.E.J. (2002) The structure and function of complex networks, SIAM Rev, vol. 74, pp. 47–97.
- Travers, J. and Milgram, S. (1969) An experimental study of the small world problem, Sociometry, vol. 32, pp. 425–442.
- Watts, D.J. (1999) Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Studies in Complexity, Princeton University Press.
Reproduced from Mathematics Today, April 2016
Download the article, Small Worlds by Design (pdf)