Nätverkscentralitet 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ål 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 grupp (täckning och mellanhet) centralitet, som är en funktion av de kortaste vägar som passerar genom en uppsättning noder, genom att lägga kanter till nätverket. Flera varianter av problemet, som är både NP-hård och APX-hård, introduceras. Vi presenterar en girig algoritm, och ännu snabbare provtagning algoritmer, för grupp centralitet maximering med teoretiska kvalitetsgarantier under realistiska begränsningar. De experimentella resultaten visar att våra provtagningsalgoritmer överträffar den bästa baslinjelösningen när det gäller centralisering med upp till 5 gånger samtidigt som de är 2-3 storleksordningar snabbare än vår giriga strategi.
I REF, Medya et al. Försök att maximera nodcentraliteten genom att lägga till kanter till grafen.
Group Centrality Maximization via Network Design
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}