Motivering: Analog till biologisk sekvensjämförelse, att jämföra cellulära nätverk är ett viktigt problem som kan ge insikt i biologisk förståelse och behandling. Av tekniska skäl är det ogenomförbart att jämföra stora nät, och därför har man sökt heuristik, såsom gradfördelning, klustringskoefficient, diameter och relativ grafletfrekvensfördelning. Det är lätt att visa att två nätverk är olika genom att helt enkelt visa en kort lista över egenskaper där de skiljer sig åt. Det är mycket svårare att visa att två nätverk är likartade, eftersom det kräver att de visar sin likhet i alla sina exponentiellt många egenskaper. Det är tydligt att det är datormässigt oöverkomligt att analysera alla nätverksegenskaper, men ju större antal begränsningar vi inför när det gäller att bestämma nätverkens likhet, desto mer sannolikt är det att nätverken verkligen kommer att vara likartade. Resultat: Vi inför ett nytt systematiskt mått på ett näts lokala struktur som medför ett stort antal likhetsbegränsningar för nätverk som jämförs. I synnerhet generaliserar vi gradfördelningen, som mäter antalet noder "touching" k kanter, i fördelningar som mäter antalet noder "touching" k graflets, där graflets är små anslutna icke-isomorpha subgraphs av ett stort nätverk. Vårt nya mått på nätverk lokal struktur består av 73 graflet grad fördelningar av graflets med 2, 3, 4, och 5 noder, men det är lätt att förlänga till ett större antal begränsningar (dvs. graflets), om nödvändigt, och förlängningarna begränsas endast av den tillgängliga CPU. Dessutom visar vi ett sätt att kombinera 73 graflet grad fördelningar i ett nät "avtal" åtgärd som är ett tal mellan 0 och 1, där 1 innebär att nätverk har identiska distributioner och 0 innebär att de är långt ifrån varandra. Baserat på denna nya nätverksavtal åtgärd, visar vi att nästan alla av de fjorton eukaryotiska PPI-nätverk, inklusive mänskliga, som härrör från olika hög-genomströmning experimentella tekniker, liksom från curerade databaser, bättre modelleras av geometriska slumpmässiga grafer än av Erdos-Renyi, slumpmässig skala-fri, eller Barabasi-Albert skala-fria nätverk. Tillgänglighet: Programvara körbara är tillgängliga på begäran.
Ett relaterat problem är att beräkna den "graphlet frekvensfördelning", som generaliserar graden distribution REF.
Biological network comparison using graphlet degree distribution
{'venue': 'Bioinformatics 2007 23: e177-e183', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Biology', 'Medicine']}