{"entities":{"Q655424":{"pageid":657273,"ns":120,"title":"Item:Q655424","lastrevid":63363798,"modified":"2026-04-11T12:22:05Z","type":"item","id":"Q655424","labels":{"en":{"language":"en","value":"Bounded budget betweenness centrality game for strategic network formations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5994301"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$FB03A41E-6797-4404-A099-AE42E30F7AFA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a5ae451c2dd7712b740c24b8e84851d86837e9c","datavalue":{"value":{"text":"Bounded budget betweenness centrality game for strategic network formations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q655424$C3DF074D-E565-4FB7-80DD-85C26D5DCBE4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"afb53c5a500aeb9293565c02b263b11af897762d","datavalue":{"value":"1244.91020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$193A2456-C869-419D-9970-88D37DD59F0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"33eca84811d4a29f62ca104a206cba28f2ff4f87","datavalue":{"value":{"entity-type":"item","numeric-id":655423,"id":"Q655423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$3AF88D0E-E7BF-4DD9-80B3-3447A9CBDA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"40f348cd0e5114af7bd9976e7ada38659459e9c4","datavalue":{"value":{"entity-type":"item","numeric-id":407512,"id":"Q407512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$42B6554A-2657-4177-A334-E3991D4E883C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"064c209d3b35f740f69a5c202f710f08e22a4e05","datavalue":{"value":{"entity-type":"item","numeric-id":248950,"id":"Q248950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$CD2694F7-8862-469D-9C66-A3CD52353537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5045a733ac4426fa65146f5f6a6eeb54c8c0c7e3","datavalue":{"value":{"entity-type":"item","numeric-id":312467,"id":"Q312467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$BEF421EB-4532-4960-9736-C61C86C1C824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8adda5b8dbcb6885b99a8d17a35fb4eb36ba9eae","datavalue":{"value":{"entity-type":"item","numeric-id":376401,"id":"Q376401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$1104F6CF-2700-4629-8FF7-0F12C45D3866","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$AD874610-92E7-48A7-9C72-73A7A5D235B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd27d2961557708e7c2573aeb1bdd7381f0f8830","datavalue":{"value":{"time":"+2012-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q655424$C54FEE7E-2061-4510-87F8-61EA97BAF38C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ced0b0e59eef36df0d1a9f1aadf5d7845a0458dd","datavalue":{"value":"In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest path exchanges. This paper studies a strategic network formation game in which nodes build connections subject to a budget constraint in order to maximize their betweenness in the network. The betweenness definition is generalized to only count shortest paths with a length limit \\(\\ell \\) in betweenness calculation. This game is referred to as the bounded budget betweenness centrality game and denoted by \\(\\ell - \\text B^{3}\\)C game, where \\(\\ell \\) is the path length constraint parameter. Complexity and constructive existence results are provided about Nash equilibria of this game. For the nonuniform version of the game where node budgets, link costs, and pairwise communication weights may vary, it is shown that Nash equilibria may not exist and that it is NP-hard to decide whether Nash equilibria exist. For the uniform version of the game where link costs and pairwise communication weights are one and each node can build \\(k\\) links, two families of Nash equilibria are constructed based on shift graphs, and the properties of such Nash equilibria are studied. Complexity of computing best responses is also studied and it is shown that the task is polynomial for uniform \\(2- B^3C\\) games and NP-hard for other games.","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$D8737BCF-C8C5-43E1-9068-DDB9DCBDC8F0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$C279A63D-04D3-4DF9-963C-F222946B46B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bc7eb0f462deb89a5bf6af1abf9a96ba13c81d67","datavalue":{"value":"91A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$03FF6727-495B-44A7-B39E-C7F2D241E439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"510d3c71187dca01ea55ca1a3a98ebbed84a7e74","datavalue":{"value":"91D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$4AA369A3-492A-419D-9C83-3E690C120FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$B4958699-E3E1-43BA-AAD0-644770B22460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e3ec0ebb66ad9a53653ec1e19a7608e786acef46","datavalue":{"value":"90B18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$EF48D24D-281D-47BC-9B99-36D45FEC1237","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07162cdb43490f5e96a555b18f62615a7a5e5088","datavalue":{"value":"5994301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$E8DF6467-A539-4B6F-A0E3-83BD6AFF0109","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d2b1fbb53d7d0980fc13547375d10c4bbcfdd3","datavalue":{"value":"algorithmic game theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$7A9D4DC8-ED93-470F-AEB0-EBE14C9E654A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef965777f8fd02360d32bb4183d9fd9b222e1292","datavalue":{"value":"network formation game","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$299C827E-072E-409A-B664-F577D15DD6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53dde8b387b5cd23f4abb2e117e873f60004406d","datavalue":{"value":"Nash equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$0DC526DE-6F12-45D2-8D44-56C04E69D8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d77bacb8a49cc317b4624139068c475ffa57048","datavalue":{"value":"network centrality","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$C186E38D-8702-4D90-92E3-457E44733BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q655424$81321537-F0B1-490B-9E09-50A90F9E0D1B","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1412ceb6c71a23f10e8f7e008bf034264afa1496","datavalue":{"value":{"entity-type":"item","numeric-id":41444,"id":"Q41444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$EBBD9E5C-CA16-4994-9A19-5F06B8E5755E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$7AC9F1E8-137A-4551-B453-6F3357DBB884","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f23d7dd0f6e7a05fa5d0dbdb6ef723a5195edde","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.09.028","type":"string"},"datatype":"url"},"type":"statement","id":"Q655424$7422E5E3-743E-4A83-A333-D183897CD4E5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fe514879742d0e30802c5d7954f4cfaf427fe9a2","datavalue":{"value":"W2115749516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$BF304562-9B6B-4DC9-8DAE-F56A40E36D3B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecea311e03c6a9b0ee9818c3625ce4277589230d","datavalue":{"value":{"entity-type":"item","numeric-id":3581526,"id":"Q3581526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$E4370886-2CC9-4B11-AEAC-EB61F3E9691E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3359525ccc2d9369a5e903d846421e46e8603d89","datavalue":{"value":{"entity-type":"item","numeric-id":5177231,"id":"Q5177231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$E2789AFF-1BE8-4D45-B84B-4BC52D890F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a350a646df05af2cd765c289d28ce10d45e83b7d","datavalue":{"value":{"entity-type":"item","numeric-id":5834367,"id":"Q5834367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$A6171C8B-EC0B-4281-A11D-C7102DFA2A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a131055da619e2b79ae0c114a7fe46e15f49a56","datavalue":{"value":{"entity-type":"item","numeric-id":2943776,"id":"Q2943776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$84E1E9E4-D1E9-4D71-8BA5-650DB37CF2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6286d46f8268fafa9b3bc56ab15168e0c1cc14a4","datavalue":{"value":{"entity-type":"item","numeric-id":2469855,"id":"Q2469855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$BD3748DD-BF4B-490D-8816-4B29AFE5E502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c139b5bfc10176a661dacd881c96e80b54d3b2ad","datavalue":{"value":{"entity-type":"item","numeric-id":2564724,"id":"Q2564724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$96D03336-0366-4472-95AD-A9D8EC5702A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559797b0b9ccef79dba758ab3e7fdd1be8c0ec37","datavalue":{"value":{"entity-type":"item","numeric-id":5891999,"id":"Q5891999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$D932FB20-9001-4E20-B105-A0598CD24342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"549bf7b565159fbc544a249a5594a9427357db0d","datavalue":{"value":{"entity-type":"item","numeric-id":5177274,"id":"Q5177274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$3415C2D3-308E-47FB-97BE-825316E058D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d8fe8aa93a4db3cd779b63f20f6c07ebb96a29e","datavalue":{"value":{"entity-type":"item","numeric-id":5176034,"id":"Q5176034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q655424$F7CB20CD-876F-4996-B7FE-F2DDC3B5209D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f756a8d354c18a02e67ee4ab8c3954349e0b022","datavalue":{"value":"10.1016/J.TCS.2011.09.028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q655424$6ACD17CA-F5D2-4BC3-9788-935E87A1B3FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8720e52922f75195be392a0991f8c3c1383de29","datavalue":{"value":{"entity-type":"item","numeric-id":3639248,"id":"Q3639248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"943677c82869830845ec55092454e0d30768f1f2","datavalue":{"value":{"amount":"+0.9663028717041016","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q655424$2D6B4B79-3AEA-4A81-8A2C-68EFEA07CB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68d71133a894da194826be54da2d3bdad01c4880","datavalue":{"value":{"entity-type":"item","numeric-id":5891999,"id":"Q5891999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5865fd14d50cefe0dedc64c9eab5b5b178b4625a","datavalue":{"value":{"amount":"+0.7940971255302429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q655424$8A6E88CD-A33E-494A-8B9D-B057A122C506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"552d7c87227c0cdcac7b74188bcf387ace34dfbf","datavalue":{"value":{"entity-type":"item","numeric-id":5920341,"id":"Q5920341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9271bbdd2bec531e819f5d89fb402fe262e50813","datavalue":{"value":{"amount":"+0.7929180860519409","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q655424$29FC9877-DCC5-4484-9A0F-99D93F32E1B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e85893f249d31e27914202f2885d6a8a0f9fc2b5","datavalue":{"value":{"entity-type":"item","numeric-id":4962196,"id":"Q4962196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26f9e2285ed685d48b0b1b80abe20e55ffeab165","datavalue":{"value":{"amount":"+0.783604085445404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q655424$80528934-F788-4D92-BE51-D67C59DB02BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e4ee8f3e7fb5547b7babf80ce2093d03eb1d9f8","datavalue":{"value":{"entity-type":"item","numeric-id":899439,"id":"Q899439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"334aae68269896c0810f1565cf222a6b74e053b3","datavalue":{"value":{"amount":"+0.7486518621444702","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q655424$A859A82E-915A-4832-ADD0-7B5755322E4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded budget betweenness centrality game for strategic network formations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_budget_betweenness_centrality_game_for_strategic_network_formations"}}}}}