Strutture per grafici casuali con struttura
Background
[Puoi saltare questo e andare immediatamente alle Definizioni.]
Le caratteristiche cruciali di un grafico o di una rete (casuale) sono:
la distribuzione dei diplomi $p(d)$ (esponenziale, Poisson o legge di potenza)
il grado medio $\bar{d}$
il coefficiente medio di clustering $\bar{C}$
la distanza media $L$ e diametro $D$
Spesso sono necessari grafici generati casualmente per mostrare la proprietà del piccolo mondo , ad es$L\propto \log N$ e $\bar{C}$è "non piccolo". Esistono diversi modelli di grafici casuali che affrontano almeno una di queste condizioni:
- Il modello Watts-Strogatz (con reticolo ad anello regolare sottostante)
- Il modello Barabasi-Albert (con attacco preferito)
- Il modello di configurazione (con date sequenze di gradi, risp. Distribuzioni)
- Il modello di Newman (che incorpora la struttura della comunità )
Mentre il modello Watts-Strogatz e il modello Barabasi-Albert sono modifiche del modello Erdős-Rényi , e il modello Newman è una generalizzazione specifica del modello di configurazione, mi chiedo se esista già un "meta-modello" che cerca di incorporare il meglio di tutti questi modelli. (Richiesta di riferimento.)
Generalizzando sia il modello di Watts-Strogatz che quello di Newman, mi piacerebbe indagare su grafi casuali che "interpolano tra una struttura randomizzata vicina a grafi ER e [qualche grafo regolare arbitrario] " (citazione da Wikipedia ).
Per questo, mi piacerebbe avere a portata di mano una moltitudine di grafici regolari che possono
essere sistematicamente simbolizzato ed enumerato,
essere facilmente generati dal loro simbolo (cioè le loro matrici di adiacenza), e
possibilmente avere espressioni in forma chiusa per le caratteristiche del piccolo mondo $L$ e $\bar{C}$
Quali grafici regolari ho in mente possono essere spiegati più facilmente con un esempio.
Definizioni
Lascia che una configurazione di vertice sia un grafico che rappresenta un vertice $\nu$ con un numero di vicini immediati $\nu_0,\nu_2,\dots,\nu_{d-1}$ e un percorso più breve (di lunghezza arbitraria) tra ogni coppia di vicini consecutivi $\nu_i, \nu_{i+1}$. Una configurazione del vertice può essere codificata dal simbolo$(n_1.n_2.\dots.n_k)^m$ che dice, quello $\nu$ ha una laurea $d = m \cdot k$ ed è circondato da un file $m$-seguenza periodica di $n_i$-facce risp. cicli più brevi. (Questa non è altro che la definizione standard delle configurazioni dei vertici in geometria nel linguaggio della teoria dei grafi.)
Esempio:
Si dice che un vertice abbia una data configurazione del vertice $\Gamma$ quando il suo vicinato insieme a un percorso più breve tra i vicini è isomorfo a $\Gamma$. Si dice che un grafo abbia una data configurazione del vertice$\Gamma$ quando tutti i suoi vertici hanno la configurazione dei vertici $\Gamma$. Si dice che una configurazione di vertice sia realizzabile quando c'è un grafo che la possiede.
Consideriamo ora i grafi finiti in cui tutti i vertici hanno la stessa configurazione dei vertici.
Domande
Sono tutte le configurazioni dei vertici $\Gamma$realizzabile da grafici di grandezza più o meno arbitraria? Come dimostrarlo o smentirlo?
Questo ha a che fare con la domanda se tutte le configurazioni dei vertici (nel senso della geometria) che non definiscono una piastrellatura periodica della sfera (cioè un poliedro regolare) definiscono una piastrellatura periodica del piano euclideo o iperbolico.Se sono presenti configurazioni di vertici non realizzabili: come posso verificare se una data configurazione di vertici è realizzabile?
Crea un grafico con una data configurazione del vertice $\Gamma$ deve essere transitivo al vertice?
Poiché il numero (uguale) di vertici di due grafi transitivi di vertice con la stessa configurazione di vertici non garantisce che siano isomorfi: con quali mezzi generali si può definire la loro "forma", in modo che due grafi ugualmente definiti debbano essere isomorfi? (Per un esempio: vedi sotto.)
Esiste un modo sistematico per generare una matrice di adiacenza per una data configurazione e "forma" di vertice realizzabile?
Con "forma" intendo ciò che Dolbilin e Schulte chiamano "complessi di quartiere (corone)" nel loro articolo Il teorema locale per tassellature monotipiche .
Esempi
Considera la configurazione dei vertici $(4)^4$ e una "forma" definita da numeri $(4, 6)$
Quando si collegano i vertici sui lati opposti della forma, tutti i vertici hanno la stessa configurazione dei vertici $(4)^4$, inoltre il grafo risultante è transitivo al vertice:
Troviamo il diametro $D = 5$, coefficiente di clustering $\bar{C} = 0$e distanza media $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ per cui trovare un'espressione esplicita chiusa o ricorsiva (a seconda di $(n,m)$) sembra essere fattibile.
Per la "forma"
con la stessa configurazione di vertici e numero di vertici che troviamo $D = 5$ e media distanza $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
Per la "forma"
con più o meno lo stesso numero di vertici che troviamo $D = 4$ e media distanza $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
Se vuoi un coefficiente di cluster $\bar{C} = 1/2$ puoi iniziare con una configurazione dei vertici $(3.n)^m$, per esempio $(3.4)^2$:
Sfortunatamente, questa configurazione non si qualifica perché non affianca un piano ma la sfera (dando origine al cubottaedro ). Quindi devi scegliere$(3.4)^3$almeno. Disegnare una bella "forma" di una certa dimensione che possa essere trasformata in un grafo finito con configurazione dei vertici$(3.4)^m$, $m > 2$, richiede geometria iperbolica . Trovare una matrice di adiacenza è ancora più difficile, come immagino (vedi domanda 5). Anche il diametro$D$ e media distanza $L$ (come espressioni chiuse).
In alternativa, si può aggiungere un bordo a metà del file $n\cdot m$ $4$-cicli (scelti a caso) del $(4)^4$ grafico - riducendo così il diametro $D$ e media distanza $L$.
Risposte
La seguente configurazione dei vertici ha una notazione $(3.4.4.4)^1$ e dovrebbe fornire controesempi alla domanda 1 (esistenza di grafici di dimensioni arbitrarie) e alla domanda 3 (transitività dei vertici).
Ci sono solo un numero finito di grafi che realizzano questa configurazione e tutti sono finiti con al massimo 24 vertici. Esattamente due di loro sono planari, il grafo del bordo del rombicubottaedro (a sinistra) e il grafo del bordo dello pseudo-rombicubottaedro strettamente correlato (a destra). Solo il primo è transitivo al vertice.
Tutti gli altri grafici possono essere ottenuti da questi identificando i vertici. Ad esempio, l'identificazione dei vertici antipodali nel grafico a sinistra dà un "poliedro proiettivo":
Ho evidenziato la configurazione del vertice nell'immagine a destra perché non è evidente in questo disegno.
Penso che questi siano tutti i grafici con questa configurazione. Potrei sbagliarmi, ma certamente non ci sono tali grafici con più di 24 vertici.
Più in generale, potresti essere interessato al teorema locale di
- "Il teorema locale per tassellature monotipiche" di Dolbilin e Schulte
che riguarda la questione quando certe restrizioni locali implicano una simmetria globale. Di solito, fornisce unicità e transitività dei vertici, ma si applica solo se la topologia è "semplicemente connessa" (quindi, per le piastrellature della sfera, piano euclideo / iperbolico, ma non per il toro, come hai visto nella tua domanda che il grafico non è unico per$(4)^4$).
All'inizio della Sezione 3 (sotto il Teorema 3.1) affermano che la configurazione $(3.5.5.5)^1$può essere realizzato come un grafo infinito, ma non come un grafo transitivo ai vertici. Ho cercato di rintracciare questa affermazione, ma si riferiscono solo al libro "Piastrellature e modelli" che contiene letteralmente migliaia di piastrellature, e non sono riuscito a trovare quella desiderata.
Infine, la seguente configurazione $(3.4.5)^1$ non dovrebbe essere realizzabile affatto:
Per vedere ciò, si noti che il grafico deve contenere una "faccia triangolare" (poiché la configurazione lo fa). Ciascuno dei tre bordi di quel triangolo è condiviso con un quadrilatero o con un pentagono. Wlog presume che due archi siano condivisi con un quadrange. Ma questi due archi condividono un vertice, quindi questo vertice non può essere di tipo$(3.4.5)^1$.
In generale, sembra piuttosto complicato distinguere le configurazioni realizzabili da quelle non realizzabili. Come regola generale, sembra che le facce strane rappresentino un problema, analogamente a come hanno fatto nell'esempio precedente. Quindi, ad esempio, una configurazione$(\mathbf 5.8.10)^1$ non può esistere neanche per lo stesso motivo, poiché esiste una faccia pentagonale che delimita due diversi tipi di facce, e non esiste un tipo di faccia ripetuto in un vertice.
Dal momento che menzioni (nei commenti) ciò a cui sei maggiormente interessato $(3.n)^m$ (supponendo $n\ge 3$, $m\ge 2$):
Questa configurazione esiste sempre, è unica e transitiva al vertice (assumendo una "topologia semplicemente connessa", che possiamo tradurre come "il grafo è planare").
È finito solo per $(3.3)^2$( ottaedro ),$(3.4)^2$( cubottaedro ) e$(3.5)^2$( icosidodecaedro ). Puoi considerarlo "planare" per$\smash{(3.3)^3}$( piastrellatura triangolare ) e$\smash{(3.6)^2}$( piastrellatura triesagonale ) e iperbolica in tutti gli altri casi.
L'unicità e la simmetria sono essenzialmente una conseguenza del teorema locale (e del relativo teorema di estensione) menzionato prima. Ma in termini semplici: se provi a costruire un grafo con una tale configurazione di vertici, e inizi da qualsiasi vertice, e poi provi a completare la configurazione del vertice attorno a uno qualsiasi degli altri vertici, puoi farlo solo in un modo unico (davvero, provalo sulla carta). Poiché non si effettua alcuna scelta in nessuno dei passaggi (forse infinitamente numerosi), il risultato è unico.