En diskret frikopplingsprocess för finita utrymmen införs, som kallas Markov-klusterprocessen eller MCL-processen. Processen är motorn för den grafklusteralgoritm som kallas MCL-algoritmen. MCL-processen tar en stokastisk matris som ingång, och växlar sedan expansion och inflation, varje steg definiera en stokastisk matris i termer av den föregående. Expansion motsvarar kth-effekten i en stokastisk matris, där k  på N. Inflation motsvarar en parametriserad operatör, r ≥ 0, som kartlägger uppsättningen (kolumn) stokastiska matriser på sig själv. Bilden ΓrM erhålls genom att höja varje post i M till rth effekt och skala om varje kolumn för att ha summan 1 igen. I praktiken konvergerar processen mycket snabbt mot en gräns som är invariant under både matrisförökning och inflation, med kvadratisk konvergens runt gränsvärdena. Den heuristiska bakom processen är dess förväntade beteende för (Markov) grafer har kluster struktur. Processen tillämpas vanligtvis på matrisen av slumpmässiga promenader på en given graf G, och de anslutna komponenterna i (den graf som är associerad med) processen gräns generellt tillåter en kluster tolkning av G. Gränsen är i allmänhet extremt gles och iterands är sparsamma i en viktad betydelse, vilket innebär att MCL algoritmen är mycket snabb och mycket skalbar. Flera matematiska egenskaper hos MCL-processen fastställs. Framför allt har processen (och algoritmen) iterands strukturella egenskaper som generaliserar kartläggningen från processgränser till kluster. Inflationsoperatören kartlägger den klass av matriser som diagonalt liknar en symmetrisk matris på sig själv. Frasen diagonalt positiv semi-definit (dpsd) används för matriser som diagonalt liknar en positiv semi-definit matris. För r N och för M en stokastisk dpsd-matris, är bilden ΕrM återigen dpsd. Determinant ojämlikhet tillfredsställs av en dpsd matris M innebär en naturlig beställning bland de diagonala elementen i M, generalisera kartläggningen av processgränser på kluster. K är antalet slutklasser av beställningen i samband med M, och n är dimensionen av M. Detta bekräftar den osammanhängande effekten av inflationsoperatören. Nyckelord. stokastisk avkoppling, grafklustring, Markov-graf, Markov-matris, diagonal likhet, positiva semidefinita matriser, cirkulära matriser AMS-ämnesklassificeringar. 68R10, 05C85, 05C90 DOI. 10,1137/040608635 1. Inledning. Ämnet för studien är en parametriserad algebraisk process som kallas Markov Cluster Process (MCL process), som är motorn i en klusteralgoritm för grafer, följaktligen kallas MCL algoritm. Algoritmen är inget annat än ett skal där parametrar ställs in, MCL-processen beräknas och resultatet tolkas. Själva processen definieras på utrymmet för stokastiska matriser. Med tanke på en graf G använder algoritmen processen genom att tillämpa den på matrisen av slumpmässiga promenader på G. MCL-algoritmen [11, 12] tillämpades först inom området proteinfamiljsdetektering [18]. I denna inställning är proteiner noder i en graf där kantvikterna härrör från BLAST (Basic Local Alignment Search Tool) poäng mellan proteinaminosyrasekvenser. Efter [18] har algoritmen tillämpats i stor utsträckning inom bioinformatik, i en mängd olika miljöer och tillämpningar.
I REF föreslås Markov Cluster Algorithm (mcl) för klustring av viktade grafer.
Graph Clustering Via a Discrete Uncoupling Process
{'venue': 'SIAM J. Matrix Analysis Applications', 'journal': 'SIAM J. Matrix Analysis Applications', 'mag_field_of_study': ['Computer Science', 'Mathematics']}