Buren van de tweede orde

Gegeven een gerichte grafiek met een paar miljoen randen, probeer ik voor elk knooppunt te vinden:

  1. Een lijst met buren van buren (laten we ze two_nei ) noemen.

  2. Het aantal gemeenschappelijke buren met elk van de two_nei (genaamd cn ).

De manier waarop ik dit probleem benader, is:

  1. Een dict maken met elk knooppunt als de sleutel en een lijst met alle buren als de waarde ( neighbor_dictionary ).

  2. Een dict maken met elk knooppunt als de sleutel en een lijst die alle buren van buren bevat ( two_nei voor dit knooppunt ) als de waarde ( second_dictionary ).

  3. Nu wil ik een lijst maken (voor het gebrek aan weten wat te doen), met een dict voor elk knooppunt in de grafiek. Elk van deze woordenboeken zal elke two_nei van het knooppunt als de sleutel bevatten en de waarde zal het aantal gemeenschappelijke buren zijn dat ze hebben.

Zoals u kunt zien, wordt dit gemakkelijk gecompliceerd. Ik weet zeker dat er een eenvoudiger en elegantere manier is om dit in python te doen. Ik ben een wiskundige en ik heb geen klassen gehad in zowel datastructuren als algoritmen, maar ik weet zeker dat we wachtrijen zouden kunnen gebruiken om dit uit te werken.

Alle hulp wordt zeer op prijs gesteld.

0
Networkx is gemakkelijk in de omgang en goed gedocumenteerd. scipy.sparse.csgraph is ontworpen voor grote grafieken (tot 2 ** 31 hoekpunten, geloof ik), kort, nieuw en opwindend. Networkx heeft een functie voor export naar SciPy, doorzoek de documentatie.
toegevoegd de auteur Fred Foo, de bron

1 antwoord

Hier is een functie die het aantal gedeelde tweede buren van twee knooppunten in een grafiek retourneert. Het gebruikt networkx voor de grafiek. Afhankelijk van hoeveel gegevens er in elk knooppunt zijn en hoe dicht uw grafiek is verbonden, werkt dit mogelijk niet omdat het potentieel grote sets in het geheugen creëert.

def num_shared_second_neighbors(graph, node1, node2):
    """number of second neighbors shared by node1 and node2 in graph"""
    return len(set(second_neighbors(graph, node1)).intersection(set(second_neighbors(graph, node2))))

def second_neighbors(graph, node):
    """                                                                                                                          
    a generator that yeilds second neighbors of node in graph                                                                    
    neighbors are not not unique!                                                                                                
    """
    for neighbor_list in [graph.neighbors(n) for n in graph.neighbors(node)]:
        for n in neighbor_list:
            yield n

De functie second_ neighbors is een generator die niet-unieke tweede buren van een knoop oplevert door een eenvoudige grafiek te maken. De functie num_shared_second_neighbors retourneert eenvoudig het aantal knooppunten in de kruising van de sets van seconden buren van twee knooppunten.

2
toegevoegd