Att uppskatta den relativa betydelsen av hörn och kanter är en grundläggande fråga i analysen av komplexa nätverk, och har funnit omfattande tillämpningar i olika aspekter, såsom sociala nätverk, kraftnät och biologiska nät. De flesta tidigare arbeten fokuserar på mätvärden av vertex betydelse och metoder för att identifiera kraftfulla hörn, medan relaterade arbete för kanter är mycket mindre, särskilt för viktade nätverk, på grund av den beräkningsutmaning. I detta dokument föreslår vi att man använder det välkända Kirchhoff-indexet som mått på kantcentralitet i viktade nätverk, som kallas "Kirchhoff edge centrality". Det Kirchhoff index för ett nätverk definieras som summan av effektiva motstånd över alla vertex par. Centraliteten i en kant e återspeglas i ökningen av Kirchhoff index av nätverket när kanten e är delvis avaktiverad, kännetecknas av en parameter  på. Vi definierar två likvärdiga åtgärder för  ska-Kirchoff edge centrality. Båda är globala mått och har en bättre diskriminerande effekt än vanliga åtgärder, baserade på lokal eller partiell strukturell information om nätverk, t.ex. Kant emellan och spänna kanten centralitet. Trots de starka fördelarna med Kirchhoff index som ett centralitetsmått och dess breda tillämpningar, beräkning av det exakta värdet av Kirchhoff kant centralitet för varje kant i en graf är beräkningskrävande. För att lösa detta problem presenterar vi en effektiv algoritm för att beräkna dess - approximation för alla m-kanter i nästan linjär tid i m. Den föreslagna "-Kirchhoff edge centrality" är den första globala metriska av egg betydelse som kan vara bevisligen ungefärlig i nästan linjär tid. Dessutom, enligt kantcentraliteten "Kirchhoff", presenterar vi en "Kirchhoff vertex centrality measure", samt en snabb algoritm som kan beräkna - ungefärlig Kirchhoff vertex centrality för alla n hörn i nästan linjär tid i m.
En delmängd av författarna till detta dokument (Li och Zhang) nyligen REF använde en uppdelning-och-konquer metod för att beräkna, för varje kant e, summan av effektiva motstånd mellan alla vertex par i grafen där e tas bort.
Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}