MATLAB: Schnelle Berechnung von Adamic-Adar Score

Question

Ich habe eine Adjazenz-Matrix eines Netzwerks und möchte den Adamic-Adar-Score berechnen. Es ist folgendermaßen definiert: Für jedes Kantenpaar x und y sei z einer ihrer gemeinsamen Nachbarn und | z | ist der Grad des Nachbarn.

Jetzt wird die Punktzahl als Summe über alle gängigen Nachbarn z definiert:

this paper, page 3 Siehe zum Beispiel.

Ich habe einen kleinen Algorithmus für MATLAB geschrieben, aber es verwendet zwei for-Schleifen. Ich bin überzeugt, dass es viel schneller gemacht werden kann, aber ich weiß nicht wie. Könnten Sie bitte Wege aufzeigen, wie Sie das beschleunigen können?

% the entries of nn will always be 0 or 1, and the diagonal will always be 0 
nn=[0 0 0 0 1 0; ... 
    0 0 0 1 1 0; ... 
    0 0 0 0 1 0; ... 
    0 1 0 0 0 1; ... 
    1 1 1 0 0 0; ... 
    0 0 0 1 0 0]; 

deg=sum(nn>0); 
AAScore=zeros(size(nn)); 

for ii=1:length(nn)-1 
    for jj=ii+1:length(nn) 
     NBs=nn(ii,:).*nn(jj,:); 
     B=NBs.*deg; 
     C=B(B>1); 
     AAScore(ii,jj)=sum(1./log(C)); 
    end 
end 
AAScore 

Ich würde jeden Vorschlag, danke!

---

Vergleich Runtimes

Mein nn hat ~ 2% Einträge, so kann es durch angenähert werden:

kk=1500; 
nn=(rand(kk)>0.98).*(1-eye(kk)); 

• Mein Doppel für: 37,404445 Sekunden.
• Divakars erste Lösung: 58.455826 Sekunden.
• Divakars aktualisierte Lösung: 22,333510 Sekunden.

Answer 1

Zunächst, erhalten Sie die Indizes in der Ausgabe-Array, die gesetzt werden würde, d. H. Nicht-Nullen. Mit Blick auf den Code konnten wir feststellen, dass wir im Grunde AND-ing jeder Zeile von der Eingabematrix nn gegen jede andere Zeile ausführen. In Anbetracht der Tatsache, dass es sich um 1s und 0s handelt, führt dies im Wesentlichen zu einer Matrixmultiplikation. Die Nicht-Nullen im Ergebnis der Matrixmultiplikation würden also die Stellen in der Ausgangsmatrix der quadratischen Matrix angeben, an denen die Berechnung benötigt wird. Dies sollte effizient sein, da wir über kleinere Elemente iterieren würden. Obendrein, da wir eine obere dreieckige Matrixausgabe erhalten, sollte dies die Berechnungen weiter reduzieren, indem eine Maske mit triu(...,1) verwendet wird.

diese Ideen verfolgt, hier ist eine Implementierung -

[R,C] = find(triu(nn*nn.'>0,1)); 
vals = sum(1./log(bsxfun(@times,nn(R,:).*nn(C,:),deg)),2); 
out=zeros(size(nn)); 
out(sub2ind(size(out),R,C)) = vals; 

---

Für einen Fall mit Eingangsmatrix nn ist weniger sparsey und wirklich riesig, würden Sie den Engpass fühlen bsxfun(@times,nn(R,:).*nn(C,:),deg) bei der Berechnung. In einem solchen Fall können Sie diese R,C Indizes direkt verwenden, um die Berechnung für die Aktualisierung der jeweiligen ausgewählten Stellen im Ausgabe-Array durchzuführen.

So eine alternative Implementierung wäre -

[R,C] = find(triu(nn*nn.',1)); 
out=zeros(size(nn)); 
for ii =1:numel(R) 
    out(R(ii),C(ii)) = sum(1./log(nn(R(ii),:).*nn(C(ii),:).*deg)); 
end 

Ein mittlerer Boden wahrscheinlich durch Anfahren mit dem R,C Indizes estabilshed zwischen den beiden oben genannten Ansätzen werden könnte, dann Stücke von Reihen aus nn(R,:) und entsprechenden Auswahl auch solche von nn(C,:) und die vektorisierte Implementierung über diese Blöcke iterativ mit geringerer Komplexität verwenden. Das Einstellen der Chunk-Größe könnte schwierig sein, da dies weitgehend von den Systemressourcen, der Größe der verwendeten Eingangsmatrix und der Spärlichkeit davon abhängen würde.