Node centrality åtgärder är viktiga i ett stort antal grafapplikationer, från sökning och rankning till sociala och biologiska nätverksanalys. I detta papper studerar vi nodcentralitet för mycket stora grafer, upp till miljarder noder och kanter. Olika definitioner av centralitet har föreslagits, alltifrån mycket enkla (t.ex. nodgrad) till mer detaljerade. Det finns dock flera utmaningar att mäta centraliteten i miljarder diagram. Många av de "traditionella" definitionerna som närhet och mellanhet var inte utformade med skalbarhet i åtanke. Därför är det mycket svårt, om inte omöjligt, att beräkna dem både exakt och effektivt. I detta dokument föreslår vi centraliserade åtgärder som lämpar sig för mycket stora grafer, samt skalbara metoder för att effektivt beräkna dem. Mer specifikt föreslår vi effektiv närhet och LINERANK som är utformade för miljarder skala grafer. Vi utvecklar också algoritmer för att beräkna de föreslagna centralitetsåtgärderna i MAPREDUCE, ett modernt paradigm för storskalig, distribuerad databehandling. Vi presenterar omfattande experimentella resultat på både syntetiska och verkliga dataset, som visar skalbarheten av vårt förhållningssätt till mycket stora grafer, samt intressanta fynd och avvikelser.
Närheten är en "traditionell" definition av centralitet, och därför var den inte "utformad med skalbarhet i åtanke", som anges i REF.
Centralities in Large Networks: Algorithms and Observations
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}