Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T10:54:12.311Z Has data issue: false hasContentIssue false
  • English
  • Français

Vulnerability and power on networks

Published online by Cambridge University Press:  16 February 2015

ENRICO BOZZO ,
MASSIMO FRANCESCHET  and
FRANCA RINALDI
ENRICO BOZZO
Affiliation:
Department of Mathematics and Computer Science, University of Udine, Udine, Italy (e-mail: [email protected], [email protected], [email protected])
MASSIMO FRANCESCHET
Affiliation:
Department of Mathematics and Computer Science, University of Udine, Udine, Italy (e-mail: [email protected], [email protected], [email protected])
FRANCA RINALDI
Affiliation:
Department of Mathematics and Computer Science, University of Udine, Udine, Italy (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Inspired by socio-political scenarios, like dictatorships, in which a minority of people exercise control over a majority of weakly interconnected individuals, we propose vulnerability and power measures defined on groups of actors of networks. We establish an unexpected connection between network vulnerability and graph regularizability. We use the Shapley value of coalition games to introduce fresh notions of vulnerability and power at node level defined in terms of the corresponding measures at group level. We investigate the computational complexity of computing the defined measures, both at group and node levels, and provide effective methods to quantify them. Finally we test vulnerability and power on both artificial and real networks.

Keywords

centrality measuresrobustnessregularizable graphs2-vertex cover2-matchinginteger linear programmingcoalitional gamesShapley value
Type
Research Article
Information
Network Science , Volume 3 , Issue 2 , June 2015 , pp. 196 - 226
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Berge, C. (1978). Regularizable graphs I. Discrete Mathematics, 23, 85–89.CrossRefGoogle Scholar
Berge, C. (1981). Some common properties for regularizable graphs, edge-critical graphs and B-graphs. In Saito, N., & Nishizeki, T. (Eds.), Graph theory and algorithms. Lecture Notes in Computer Science, vol. 108 (pp. 108–123). Berlin: Springer.CrossRefGoogle Scholar
Berkman, L. F., & Glass, T. (2000). Social integration, social networks, social support, and health. In Berkman, L. F., & Kawachi, I. (Eds.), Social epidemiology. New York: Oxford University Press.CrossRefGoogle Scholar
Bonacich, P. (1987). Power and centrality: A family of measures. American Journal of Sociology, 92 (5), 1170–1182.CrossRefGoogle Scholar
Burt, R. S. (2004). Structural holes and good ideas. American Journal of Sociology, 110 (2), 349–399.CrossRefGoogle Scholar
Cobb, N. K., Graham, A. L., & Abrams, D. B. (2010). Social network structure of a large online community for smoking cessation. American Journal Public Health, 100 (7), 1282–1289.CrossRefGoogle ScholarPubMed
Everett, M. G., & Borgatti, S. P. (1999). The centrality of groups and classes. Journal of Mathematical Sociology, 23 (3), 181–201.CrossRefGoogle Scholar
Franceschet, M. (2011). PageRank: Standing on the shoulders of giants. Communications of the ACM, 54 (6), 92–101.CrossRefGoogle Scholar
Godsil, C., & Royle, G. F. (2001). Algebraic graph theory. New York: Springer.CrossRefGoogle Scholar
Grofman, B., & Owen, G. (1982). A game-theoretic approach to measuring centrality in social networks. Social Networks, 4, 213–224.CrossRefGoogle Scholar
Grötschel, M., Lovász, L., & Schrijver, A. (1988). Geometric algorithms and combinatorial optimization. Heidelberg: Springer.CrossRefGoogle Scholar
Hayes, B. (2006). Connecting the dots. American Scientist, 94 (5), 400–404.CrossRefGoogle Scholar
Heaney, C. A., & Israel, B. A. (2008). Social networks and social support. In Glanz, K., Rimer, B. K., & Viswanath, K. (Eds.), Health behavior and health education: Theory, research and practice. San Francisco: Jossey-Bass.Google Scholar
Hoory, S., Linial, N., & Wigderson, A. (2006). Expander graphs and their applications. Bulletin of the American Mathematical Society, 43, 439–561.CrossRefGoogle Scholar
Iwata, S. (2008). Submodular function minimization. Mathematical Programming, 112, 45–64.CrossRefGoogle Scholar
Kets, W., Iyengar, G., Sethi, R., & Bowles, S. (2011). Inequality and network structure. Games and Economic Behavior, 73 (1), 215–226.CrossRefGoogle Scholar
Khachiyan, L. (1980). Polynomial algorithms for linear programming. Ussr Computational Mathematics and Mathematical Physics, 20, 51–68.CrossRefGoogle Scholar
Lovász, L., & Plummer, M. D. (1986). Matching theory. Annals of discrete mathematics, vol. 29. Amsterdam: North Holland.Google Scholar
Michalak, T. P., Aadithya, K. V., Szczepański, P. L., Ravindran, B., & Jennings, N. R. (2013). Efficient computation of the Shapley value for game-theoretic network centrality. Journal of Artificial Intelligence Research, 46, 607–650.CrossRefGoogle Scholar
Newman, M. E. J. (2010). Networks: An introduction. Oxford: Oxford University Press.CrossRefGoogle Scholar
Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69, 026113.CrossRefGoogle ScholarPubMed
Osborne, M. J., & Rubinstein, A. (1994). A course in game theory. Annals of discrete mathematics. Cambridge, MA: MIT Press.Google Scholar
Pulleyblank, W. R. (1979). Minimum node covers and 2-bicritical graphs. Mathematical Programming, 17, 91–103.CrossRefGoogle Scholar
Schrijver, A. (2003). Combinatorial optimization - polyhedra and efficiency. Berlin: Springer.Google Scholar
Shapley, L. S. (1971). Cores of convex games. International Journal of Game Theory, 1 (1), 11–26.CrossRefGoogle Scholar
Suri, N., & Narahari, Y. (2010). A Shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering, 99, 1–18.Google Scholar
Szczepański, P. L., Michalak, T., & Rahwan, T. (2012). A new approach to betweenness centrality based on the Shapley value. Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 239–246.Google Scholar
Tutte, W. T. (1953). The 1-factors of oriented graphs. Proceedings of the American Mathematical Society, 4, 922–931.CrossRefGoogle Scholar
van den Brink, R., & Gilles, R. P. (1994). A social power index for hierarchically structured populations of economic agents. In Gilles, R. P., & Ruys, P. H. M. (Eds.), Imperfections and behavior in economic organizations. Theory and Decision Library, vol. 11 (pp. 279–318). Netherlands: Springer.CrossRefGoogle Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.CrossRefGoogle ScholarPubMed