Introduction
A common problem in numerical simulation research with shared intentions where an interaction network, g (N,E) is specified, is to identify connected sub-graphs S ⊆ N of size k. It is these connected sub-graphs S which may jointly update their actions under the assumption of the sharing of intentions.
The complexity of enumerating feasible coalitions of size k depends strongly on the topology of the network.
For example, if g is the complete graph, then there are {|N| choose k} such coalitions, which for the networks of say |N| = 256 and coalitions of size k equal to 4 or 8, gives rise to over 174 million and over 4E14 ways of forming S respectively.
On the other hand, for a 2−regular ring network, there are only |N| feasible coalitions of size k, since the topology constrains the composition of S to |N| consecutive index sets, each with a different starting vertex.
However, in most cases, even a small amount of density at the local level complicates the picture dramatically. For this reason, the modeller has a choice of whether to pre-build a library of coalitions for a given g and coalition size k or construct coalitions as needed at run-time. We demonstrate the latter method below.
A simple coalition formation algorithm
As in shared intentions and social norms we enumerate a simple coalition formation algorithm. An important property of such an algorithm is that, given a randomly selected vertex, i, coalition size k, and graph g, the algorithm f: {i,k,g} → S_i should produce with equal probability any sub-graph S of all possible connected sub-graphs which include i, S_i. The algorithm below satisfies this condition.
Step 1: Let the resultant sub-graph be vertex set s ⊆ S. Choose a starting vertex, i ∈ N. Initialise s = {i}. In Fig. 1, vertex a has been selected. So, set s = {a}. If |s| = k, stop and return s, else continue.
Step 2: Construct an adjacency vertex set to s, a ⊆ N\s comprising the set of adjacent vertices to members of a, which are not already in s. In Fig. 2 four such vertices have been identified, so set a = {b,c,i,h}.
Step 3: Choose a single vertex from a, to grow s by one. In Fig. 3, vertex i has been chosen, so s = {a,i}. If |s| = k, stop and return s, else continue, by re-constructing a (Step 2), here a = {b,c,h,u,t}.
Step 4: Repeat Step 3 until stop. In Fig. 4 we follow one more iteration to build a k = 3 size connected sub-graph, s = {a,i,h} (and a = {c,b,u,t,r,s}).