Abstrakt. -Vi introducerar en ny distribuerad algoritm för att anpassa grafer eller hitta substrukturer inom en given graf. Det är baserat på hålighetsmetoden och används för att studera maximal-klick och graf-anpassning problem i slumpmässiga grafer. Algoritmen gör det möjligt att analysera stora grafer och kan hitta tillämpningar inom områden som beräkningsbiologi. Som ett bevis på konceptet använder vi vår algoritm för att anpassa likhetsdiagram över två interagerande proteinfamiljer som är involverade i bakteriell signaltransduktion, och för att förutsäga faktiskt interagerande proteinpartners mellan dessa familjer. Under det senaste årtiondet har användningen av grafer för beskrivning av relationer mellan komponenter i komplexa system blivit allt populärare [1]. Den största delen av den nuvarande litteraturen koncentreras dock på lokala egenskaper som nodgrader (beräkningsmässigt tillgängliga), medan fullt utnyttjande av större näts mer globala egenskaper fortfarande ofta är svårfångat på grund av deras inneboende algoritmiska komplexitet. De flesta studier av globala egenskaper kräver att man löser NP-hårda problem eller ännu svårare problem om någon form av osäkerhet eller brist på information ingår i definitionen av problemet. I båda fallen måste heuristiska algoritmer utvecklas. Särskilda exempel, som omfattas av denna artikel, inkluderar jämförelse av två olika nätverk, det s.k. graf-alignment problem (GA) [2] [3] [4], och sub-graf isomorfism (SGI), som ett särskilt fall som vi anser att den allmänt studerade maximal-clique problem [5] [6] [7]. Nyligen har det funnits ett stort intresse för distribuerade algoritmer för att hantera optimeringsproblem över nätverk. I samband med statistisk fysik har en ny generation algoritmer utvecklats (t.ex. [8, 9] ) som har visat lovande resultat i flera ansökningar (för en granskning, se [10] ). Dessa tekniker är baserade på den så kallade hålighetsmetoden och är kända som meddelandepasserande algoritmer (MP). De är helt fördelade och lätta att köra på parallella maskiner. Ett nytt resultat i detta ramverk är en algoritm för att hitta en ansluten delgraf av en given graf som optimerar en given faktoriserad kostnadsfunktion [11]. Här strävar vi efter att ta ett steg framåt genom att införa nya tekniker för SGI och GA. Vi utvecklar två alternativa MP-strategier och testar deras prestanda på tre urvalsproblem. De två första är väldefinierade teoretiska riktmärken, där våra resultat kan jämföras med rigorösa gränser: (i) det maximala klickproblemet i slumpmässiga grafer för SGI-problemet; och (ii) anpassningen av två slumpmässiga grafer av kontrollerad likhet. Det tredje provet problem anses som en proof-of-concept tillämpning i beräkningsbiologi: Vi studerar (iii) anpassningen av likhet nätverk av två interagerande protein-domäner som är involverade i bakteriell signalöverföring, för att identifiera faktiska signalvägar. Detta fall, som omfattar stora nätverk av >2500 noder, utnyttjar co-evolutionära processer mellan interagerande proteiner för att identifiera interaktionspartner [12]. Modellen -Både problemen, SGI och GA, kan sättas in i den gemensamma ramen för att matcha två diagram av möjligen olika storlek. Låt G = (V, E, w) och G ′ = (V ′, E ′, w ′ ) vara två viktade grafer med noder V, V ′, kanter E, E ′ och kantvikter w, w ′. I de tillämpningar som visas i denna bokstav, vikter är icke-negativa, men detta är inte ett nödvändigt villkor för tillämpligheten av meddelandepasserande algoritmer. I fallet med oviktade grafer, antar vi w och w ′ för att beskriva adjacency matriser, dvs.. Vikter är en om en kant finns mellan två hörn, och noll annars. Ytterligare mer betecknar vi nodnumret med N =  och V (N ), och kantnumret med M =,, (M =,,, ),,,,,,,, ),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ),,,,,,,,,,,, ),,,,,,,,,,,,,,, ),,,,,,,,,,,,,, ),,,,,,,,,,,.,,,,,,,,,,,,,,,,,,,.,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ),,,,,,,,,,,,,,,,,,,,,,,,,,,,  Grannar till en nod jag är monterade i ∂i. För att underlätta notifieringen hänvisar man alltid till G (särskilt knutpunktsindex).
Även om både REF och detta arbete delar användningen av en BP metod, faktorgrafen och algoritmerna är olika.
Aligning graphs and finding substructures by a cavity approach
{'venue': '2010 Europhys. Lett. 89 37009', 'journal': None, 'mag_field_of_study': ['Physics', 'Biology', 'Computer Science']}