Detta arbete behandlar grafbaserad semi-övervakad klassificering och mellanhet beräkning i stora, glesa, nätverk (flera miljoner noder). Syftet med semi-övervakad klassificering är att tilldela en etikett till omärkta noder med hjälp av hela topologin i grafen och den märkning som står till vårt förfogande. Två metoder utvecklas för att undvika explicit beräkning av parvis närhet mellan noderna i grafen, vilket skulle vara opraktiskt för grafer som innehåller miljontals noder. Den första metoden beräknar direkt, för varje klass, summan av likheterna mellan noderna att klassificera och de märkta noderna i klassen som ursprungligen föreslogs i [1, 2]. Med detta tillvägagångssätt utvecklas två algoritmer som utnyttjar olika toppmoderna kärnor på en graf. Samma strategi kan också användas för att beräkna en mellanhetsåtgärd. Den andra metoden fungerar på en spaljé struktur byggd från partiska slumpmässiga promenader på grafen, utvidga en idé infördes [3]. Dessa slumpmässiga promenader gör det möjligt att definiera en partisk avgränsad mellanhet för noderna av intresse, definieras separat för varje klass. Alla föreslagna algoritmer har en linjär beräkningstid i antalet kanter, och är därför tillämpliga på stora glesa nätverk. De är empiriskt validerade på medelstora standarddatamängder och visar sig vara konkurrenskraftiga med den senaste tekniken. Slutligen behandlade vi en ny datauppsättning, som görs tillgänglig för benchmarking, för klassificering i flera klasser i ett stort nätverk: USA patent citeringsnätverk som innehåller 3M noder (av sex olika klasser) och 38M kanter. De tre föreslagna algoritmerna uppnår konkurrenskraftiga resultat (ca 85% klassificeringsfrekvens) på detta stora nätverk - de klassificerar de omärkta noderna inom några minuter på en standardarbetsplats.
Mantrach m.fl. REF utforma två iterativa algoritmer som kan tillämpas i nätverk med miljontals noder för att undvika beräkning av parvisa likheter mellan noder.
Semi-supervised Classification and Betweenness Computation on Large, Sparse, Directed Graphs
{'venue': 'Pattern Recognit.', 'journal': 'Pattern Recognit.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}