Mellanhetscentralitetsindexet är avgörande för analysen av sociala nätverk, men kostsamt att beräkna. För närvarande kräver de snabbaste kända algoritmerna tid och utrymme, där n är antalet aktörer i nätverket. Motiverad av det snabbt växande behovet av att beräkna centralitetsindex på stora, men ändå mycket glesa, nätverk, introduceras nya algoritmer för mellanhet i detta dokument. De kräver O(n + m) utrymme och körs i O(nm) och O(nm + n 2 log n) tid på oviktade och viktade nätverk, respektive, där m är antalet länkar. Experimentella bevis läggs fram för att detta avsevärt ökar antalet nätverk för vilka centralitetsanalys är möjlig.
I REF införde författarna nya algoritmer för beräkning av vertex mellanhet, som utförs i O(nm) och O(nm + n 2 log n) tid för oviktade respektive viktade nätverk.
A Faster Algorithm for Betweenness Centrality
{'venue': 'Journal of Mathematical Sociology', 'journal': None, 'mag_field_of_study': ['Mathematics']}