Effektgrafanalys - Power graph analysis
I beräkningsbiologi , effekt graf analys är en metod för analys och representation av komplexa nätverk . Effektgrafanalys är beräkning, analys och visuell representation av en effektgraf från en graf ( nätverk ).
Effektgrafanalys kan ses som en förlustfri komprimeringsalgoritm för grafer. Den utökar grafsyntaxen med representationer av klickningar , cyklar och stjärnor . Komprimeringsnivåer på upp till 95% har erhållits för komplexa biologiska nätverk .
Hypergrafer är en generalisering av grafer där kanter inte bara är par av noder utan godtyckliga n-tupler . Effektgrafer är inte en annan generalisering av grafer, utan istället en ny representation av grafer som föreslår en förskjutning från "noden och kanten" -språket till en som använder klick, bicliques och stjärnor som primitiv.
Effektgrafer
Grafisk representation
Grafer ritas med cirklar eller punkter som representerar noder och linjer som förbinder par av noder som representerar kanter . Effektgrafer förlänger syntaxen för grafer med effektnoder , som ritas som en cirkel som omsluter noder eller andra kraftnoder , och kraftkanter , som är linjer mellan kraftnoder.
Bicliques är två uppsättningar noder med en kant mellan varje medlem i en uppsättning och varje medlem i den andra uppsättningen. I ett effektdiagram representeras en biclique som en kant mellan två effektnoder.
Cliques är en uppsättning noder med en kant mellan varje par noder. I en effektgraf representeras en klick av en effektnod med en slinga .
Stjärnor är en uppsättning noder med en kant mellan varje medlem i den uppsättningen och en enda nod utanför uppsättningen. I en effektgraf representeras en stjärna av en kraftkant mellan en vanlig nod och en effektnod.
Formell definition
Givet en graf där är den uppsättning av noder och är den uppsättning av kanter, en effekt graf är en graf som definieras på effekt uppsättning av kraftnoder som är anslutna till varandra genom kraft kanter : . Därför definieras effektgrafer på både effektmängden av noder och på kraftuppsättningen av kanterna på grafen .
Semantiken för effektgrafer är följande: om två effektnoder är anslutna med en effektkant, betyder det att alla noder i den första effektnoden är anslutna till alla noder i den andra effektnoden. På samma sätt, om en kraftnod är ansluten till sig själv med en kraftkant, betyder detta att alla noder i kraftnoden är anslutna till varandra med kanter.
Följande två villkor krävs:
- Strömnodshierarki villkor: Alla två kraftnoder är antingen avskilda, eller så ingår en i den andra.
- Strömkantsuppdelning: Det finns en kartläggning från kanterna på originalgrafen till kraftkanterna.
Analogi till Fourier -analys
Den Fourier-analys av en funktion kan ses som en omskrivning av funktionen i form av harmoniska funktioner i stället för par. Denna transformation förändrar synvinkel från tidsdomän till frekvensdomän och möjliggör många intressanta applikationer inom signalanalys , datakomprimering och filtrering. På samma sätt är Power Graph Analysis en omskrivning eller sönderdelning av ett nätverk som använder bicliques, cliques och stjärnor som primitiva element (precis som harmoniska funktioner för Fourier -analys). Den kan användas för att analysera, komprimera och filtrera nätverk. Det finns dock flera viktiga skillnader. För det första, i Fourier -analys är de två mellanslagen (tids- och frekvensdomäner) samma funktionsutrymme - men stricto sensu, effektgrafer är inte grafer. För det andra finns det inget unikt effektdiagram som representerar en given graf. Ändå är en mycket intressant klass med effektgrafer minimala effektgrafer som har de minsta effektkanterna och effektnoderna som krävs för att representera en given graf.
Minimala effektgrafer
I allmänhet finns det ingen unik minimal effektgraf för en given graf. I det här exemplet (höger) tillåter en graf med fyra noder och fem kanter två minimala effektgrafer med två effektkanter vardera. Huvudskillnaden mellan dessa två minimala effektgrafer är den högre häckningsnivån för den andra effektgrafen samt en förlust av symmetri med avseende på den underliggande grafen. Förlust av symmetri är bara ett problem i små leksaksexempel eftersom komplexa nätverk sällan uppvisar sådana symmetrier i första hand. Dessutom kan man minimera häckningsnivån men även då finns det i allmänhet inte en unik minimal effektgraf för minimal häckningsnivå.
Power graph girig algoritm
Power -grafiska giriga algoritmen bygger på två enkla steg för att utföra sönderdelningen:
Det första steget identifierar kandidatkraftnoder genom en hierarkisk gruppering av noderna i nätverket baserat på likheten mellan deras angränsande noder. Likheten mellan två uppsättningar grannar tas som Jaccard -index för de två uppsättningarna.
Det andra steget utför en girig sökning efter möjliga effektkanter mellan kandidatens effektnoder. Strömkanter som abstraherar de flesta kanterna i det ursprungliga nätverket läggs först till effektdiagrammet. Således ersätts bicliques, cliques och stjärnor stegvis med kraftkanter tills alla återstående enstaka kanter också läggs till. Kandidatkraftnoder som inte är slutpunkten för någon kraftkant ignoreras.
Modulär sönderdelning
Modulär sönderdelning kan användas för att beräkna en effektgraf med hjälp av de starka modulerna för den modulära sönderdelningen. Moduler i modulär sönderdelning är grupper av noder i en graf som har identiska grannar. En stark modul är en modul som inte överlappar med en annan modul. Men i komplexa nätverk är starka moduler mer undantaget än regeln. Därför är effektgraferna som erhålls genom modulär sönderdelning långt ifrån minimalitet. Huvudskillnaden mellan modulär sönderdelning och effektgrafanalys är tyngden av kraftgrafanalys i sönderdelande grafer, inte bara med hjälp av moduler av noder utan även moduler av kanter (klickningar, bicliques). Faktum är att effektgrafanalys kan ses som en förlustfri samtidig klustering av både noder och kanter.
Ansökningar
Biologiska nätverk
Power Graph Analysis har visat sig vara användbart för analys av flera typer av biologiska nätverk, såsom protein-protein-interaktionsnätverk , domänpeptidbindande motiv, genreglerande nätverk och homologi/paraloginätverk. Ett nätverk av signifikanta par för sjukdom-egenskaper har också nyligen visualiserats och analyserats med Power Graphs.
Nätverkskomprimering, ett nytt mått som härrör från Power Graphs, har föreslagits som ett kvalitetsmått för proteininteraktionsnätverk.
Omplacering av läkemedel
Power Graphs har också tillämpats på analysen av läkemedelsmål-sjukdomsnätverk för läkemedelspositionering .
Sociala nätverk
Power Graphs har tillämpats på storskaliga data i sociala nätverk, för community mining eller för modellering av författartyper.