Vi presenterar en ny distribuerad algoritm för att räkna alla fyra-node inducerade subgrafer i en stor graf. Dessa värden, som kallas 4-profilen, beskriver grafens konnektivitetsegenskaper och har funnit flera användningsområden som sträcker sig från bioinformatik till skräppostdetektering. Vi studerar också det mer komplicerade problemet med att uppskatta de lokala 4-profiler centrerade vid varje vertex av grafen. Den lokala 4-profilen inbäddar varje vertex i ett 11-dimensionellt utrymme som kännetecknar den lokala geometrin i dess grannskap: hörn som förbinder olika kluster kommer att ha olika lokala 4-profiler jämfört med dem som bara är en del av en tät kluster. Vår algoritm är en lokal, distribuerad meddelande-passing schema på grafen och beräknar alla lokala 4-profiler parallellt. Vi förlitar oss på två nya teoretiska bidrag: vi visar att lokala 4-profiler kan beräknas med hjälp av komprimerad två-hop information och också etablera nya koncentrationsresultat som visar att grafer kan vara avsevärt glesare och fortfarande behålla god approximation kvalitet för den globala 4-profil. Vi utvärderar vår algoritm empiriskt med hjälp av en distribuerad GraphLab implementation som vi skalade upp till 640 kärnor. Vi visar att vår algoritm kan beräkna globala och lokala 4-profiler av grafer med miljontals kanter på några minuter, vilket avsevärt förbättrar den tidigare tekniken.
Elenberg m.fl. REF presenterar en distribuerad algoritm för att räkna subgrafer av storlek 4.
Distributed Estimation of Graph 4-Profiles
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}