Abstract-Network centrality spelar en viktig roll i många tillämpningar. Centrala noder i sociala nätverk kan vara inflytelserika, driva åsikter och sprida nyheter eller rykten. I hyperlänkade miljöer, som till exempel webben, där användare navigerar via klick, får centralt innehåll hög trafik och blir måltavlor för reklamkampanjer. Även om det finns en omfattande mängd arbete med centralitet åtgärder och deras effektiva beräkning, kontrollera nodernas centralitet via nätverksuppdateringar är en nyare och utmanande uppgift. Utföra minimala ändringar i ett nätverk för att uppnå en önskad egenskap faller under paraply av nätverk design problem. Detta dokument är inriktat på att förbättra gruppen (täckning och mellanhet) centralitet av en uppsättning noder, som är en funktion av antalet kortaste vägar som passerar genom uppsättningen, genom att lägga kanter till nätverket. Vi introducerar flera varianter av problemet, som visar att de är både NP-hårda och APX-hårda. Dessutom presenterar vi en girig algoritm, och ännu snabbare provtagningsalgoritmer, för gruppcentralitetsmaximering med teoretiska kvalitetsgarantier under en begränsad miljö och goda empiriska resultat i allmänhet för flera verkliga datauppsättningar.
Medya m.fl. REF karakteriserar centralitet som ett viktigt nätmått och föreslår ändringar i nätverksstrukturen för att öka centraliteten hos en uppsättning noder för att förbättra prestandan.
Maximizing Coverage Centrality via Network Design: Extended Version
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}