Not all bridges connect: integration in multi-community networks

ABSTRACT

This paper studies structures for efficient and stable integration of multi-community networks where establishing bridges across communities incur additional link cost compared to those within communities. Building on the connections models with direct and indirect benefits, we show that the efficient structure for homogeneous cost and benefit parameters, and for communities of arbitrary size, always has a diameter no greater than 3. We further show that for non-trivial cases, integration always follows one of these three structures: single star, two hub-connected stars, and a new structure we introduce in this paper as parallel hyperstar, which is a special core/periphery structure with parallel bridges that connect the core nodes of different communities. Then we investigate stability conditions of these structures, using the standard pairwise stability, as well as post-transfer pairwise stability, a new stability notion we introduce in this paper, which allows for bilateral utility transfers. We show that while the parallel hyperstar structure can never be both efficient and pairwise stable, once post-transfer pairwise stability is used, efficiency guarantees stability. Furthermore, we show that all possible efficient structures can be simultaneously post-transfer pairwise stable. In the end, we provide some numerical results and discussion of empirical evidences.

KEYWORDS:

• Social networks
• community integration
• heterogeneous networks
• strategic network formation
• pairwise stability
• hyperstar network
• connections models

Acknowledgments

The authors would like to thank Matthew Jackson, Joel Sobel, and especially Ben Galub for their valuable comments on the earlier versions of this work. We also would like to thank Carliss Baldwin from HBS for her comments and discussions on core/periphery structures.

Notes

¹ Throughout the paper, we use community and group interchangeably.

² The second structure, two hub-connected structure, can be considered a special case of parallel hyperstar with only one bridge. However for the sake of presentation and differentiating some results we use it as a separate category.

³ This is because each new internal link increases the utility by $b(1)$ and decreases it by a maximum of $c+b(2)$.

⁴ Here we differentiate between parallel hyperstar and two hub-connected stars and assume that the parallel hyperstar has at least two bridges.

Additional information

Funding

This work was in part supported by the National Science Foundation under Grant CMMI. 1548521;Division of Civil, Mechanical and Manufacturing Innovation [1554560].