Many real-world networks, such as social networks, consist of strategic agents. The topology of these networks often plays a crucial role in determining the ease and speed with which certain information-driven tasks can be accomplished. Consequently, growing a stable network of a certain desired topology is of interest. Motivated by this, we study the following important problem: Given a certain desired topology, under what conditions would best response link alteration strategies adopted by strategic agents lead to formation of a stable network having the given topology and no other topology. This problem is the inverse of the classical network formation problem where we are concerned with determining stable topologies, given the conditions on the network parameters. We study this interesting inverse problem by proposing (1) a recursive model of network formation and (2) a utility model that captures key determinants of network formation. Building upon these models, we explore relevant topologies such as star graph complete graph, bipartite Turán graph, and multiple stars with interconnected centres. We derive a set of sufficient conditions under which these topologies uniquely emerge, study their social welfare properties and investigate the effects of deviating from the derived conditions.
AbbassiZ.HeidariH. (2011). Toward optimal vaccination strategies for probabilistic models. Proceedings of the 20th International Conference Companion on World Wide Web, Hyderabad, India. ACM, 12.
2.
AtalayE. (2013). Sources of variation in social networks. Games and Economic Behavior, (79), 106131.
3.
AumannR.MyersonR. (1988). Endogenous formation of links between players and coalitions: An application of the Shapley value. The Shapley value (pp. 175�191). Cambridge, England: Cambridge University Press.
4.
BlochF.JacksonM. (2006). Definitions of equilibrium in network formation games. International Journal of Game Theory, 34(3), 305�318.
5.
BudakC.AgrawalD.El AbbadiA. (2011). Limiting the spread of misinformation in social networks.Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India. ACM, 665�674.
6.
DhamalS.NarahariY. (2012). Forming networks of strategic agents with desired topologies. In P. Goldberg (Ed.), Lecture Notes in Computer Science. Internet and Network Economics (pp. 504511). Berlin, Heidelberg: Springer.
7.
DoreianP. (2006). Actor network utilities and network evolution. Social Networks, 28(2), 137�164.
8.
EhrhardtG.MarsiliM.Vega-RedondoF. (2006). Diffusion and growth in an evolving network. International Journal of Game Theory, 34(3), 383�397.
9.
GaneshA.MassouliL.TowsleyD. (2005). The effect of network topology on the spread of epidemics. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, Florida, USA. IEEE, 2, 1455-1466.
10.
GaoX.XiaoB.TaoD.LiX. (2010). A survey of graph edit distance. Pattern Analysis and Applications, 13(1), 113�129.
11.
GoyalS.JoshiS. (2006). Unequal connections. International Journal of Game Theory, 34(3), 319�349.
12.
GoyalG.Vega-RedondoF. (2007). Structural holes in social networks. Journal of Economic Theory, 137(1), 460�492.
13.
HellmannT.StaudiglM. (2014). Evolution of social networks. European Journal of Operational Research, 234(3), 583�596.
14.
HummonN. (2000). Utility and dynamic social networks. Social Networks, 22(3), 221249
15.
JacksonM. (2003). The stability and efficiency of economic and social networks. Advances in Economic Design, 6, 1�62.
16.
JacksonM. (2005). Allocation rules for network games. Games and Economic Behavior, 51(1), 128�154.
17.
JacksonM. (2005). A survey of network formation models: Stability and efficiency. In G. Demange M. Wooders (eds), Group formation in economics: Networks, clubs and coalitions pp. 11-57.
18.
JacksonM. (2008). Social and economic networks. New Jersey, USA: Princeton University Press.
19.
JacksonM.O.RogersB.W. (2007). Meeting strangers and friends of friends: How random are social networks? The American Economic Review, 97(3), 890�915.
20.
JacksonM.WattsA. (2002). The evolution of social and economic networks. Journal of Economic Theory, 106(2), 265-295.
21.
JacksonM.WolinskyA. (1996). A strategic model of social and economic networks. Journal of Economic Theory, 71(1), 4474.
22.
KempeD.KleinbergJ.TardosE. (2003). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, D.C., USA. ACM}, 137�146.
23.
KleinbergJ.SuriS.TardosE.WexlerT. (2008). Strategic network formation with structural holes. Proceedings of the 9th ACM Conference on Electronic Commerce, Chicago, Illinois, USA. ACM, 284-293.
24.
KonigM.D.BattistonS.NapoletanoM.SchweitzerF.The efficiency and stability of R&D networks. Games and Economic Behavior, 75(2), 694-713.
25.
McInerneyC. (2002). Knowledge management and the dynamic nature of knowledge. Journal of the American Society for Information Science and Technology, 53(12), 1009�1018.
26.
MutuswamiS.WinterE. (2002). Subscription mechanisms for network formation. Journal of Economic Theory, 106(2), 242�264.
27.
MyersonR. (1977). Graphs and cooperation in games. Mathematics of Operations Research, 2(3), 225�229.
28.
NarayanamR.NarahariY. (2011). Topologies of strategically formed social networks based on a generic value function�allocation rule model. Social Networks, 33(1), 56�69.
29.
OsborneM. (2004). An introduction to game theory (Vol. 3, no. 3). New York, NY: Oxford University Press.
30.
PantzK.ZiegelmeyerA. (2003). An experimental study of network formation. Garching, Germany, Max Planck Institute, mimeo.
31.
Van DolderD.BuskensV. (2014). Individual choices in dynamic networks: An experiment on social preferences. PloS One, 9(4), e92276.
32.
WattsA. (2001). A dynamic model of network formation. Games and Economic Behavior, 34(2), 331�341.
33.
WoodardC.ParkesD. (2003). Strategy proof mechanisms for ad hoc network formation. 1st Workshop on Economics of Peer-to-Peer Systems (P2PEcon), Berkeley, California, USA.
34.
XieF.CuiW. (2008a). Cost range and the stable network structures. Social Networks, 30(1), 100�101.
35.
XieF.CuiW.. (2008b). A note on the paper �cost range and the stable network structures�. Social Networks, 30(1) 102�103.
36.
ZengZ.TungA.WangJ.FengJ.ZhouL. (2009). Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1), 25�36.
37.
ZhangY.van der SchaarM. (2013). Strategic networks: Information dissemination and link formation among self-interested agents. IEEE Journal on Selected Areas in Communications, 31(6), 1115�1123.
