It is also interesting to elaborate on how distinct communities are
brought together to create large connected graphs. Without the connectivity between dense communities,
isolated components would not support many of the fascinating phenomena
that have been observed, notably the hugely influential small world effect [1]},
where there exist surprisingly short paths between members of the network located in different communities.
By definition,
the density of those edges connecting communities is less than the density of edges within communities. The sparsity of the
inter-community connectivity is the basis for community separation quality measures such as the modularity index, [2]}.
The relatively low number of these edges connecting communities together gives them special importance as they are critical for the
graph's connectivity. A recent study explores this network feature using examples from brain connectivity, [3]},
concluding that connection costs can explain these modular networks.
For the applications in OSNs, where companies seek
to harness the power of internet advertising, nodes which offer community traversal connections are critical targets
[4]}.
The aim of our work is therefore to give a simple and scalable methodology for defining and
discovering this type of key structure.
To be concrete,
for the remainder of this paper an edge connecting two different communities will be referred
to as a boundary edge and the nodes on either side of these edges as boundary nodes.
