Barabasi-Albert Scale-Free Graph
Informacje podstawowe
- Nazwa: Barabasi-Albert Scale-Free Graph
- Alias: BA graph, scale-free network, preferential attachment graph
- Dziedzina: Graph Theory, Complex Networks, Graph Neural Networks
- Typ: Synthetic graph data
Źródło
- URL: Generated synthetically using Barabasi-Albert algorithm
- Paper: “Statistical mechanics of complex networks” (Albert & Barabási, 2002)
- Organizacja: University of Notre Dame
- Rok: 2002
Charakterystyka
- Rozmiar: 1,000 nodes
- Parametry: m = 1 (number of edges to attach from new node)
- Klasy/Kategorie: Binary classification (generated based on node features)
- Format: Graph structure with 20-dimensional binary feature vectors
- Licencja: N/A (synthetic, generated on demand)
Opis
Barabasi-Albert model generuje scale-free graphs z power-law degree distribution poprzez mechanizm preferential attachment: nowe węzły preferują łączenie się z węzłami o już wysokim degree. Ten model lepiej odzwierciedla strukturę rzeczywistych sieci (social networks, citation networks, internet) niż modele losowe jak Erdos-Renyi.
Kluczowe właściwości:
- Power-law degree distribution: P(k) ~ k^(-γ)
- Występowanie hubs - węzłów o bardzo wysokim degree
- Small-world property - krótkie ścieżki między węzłami
- Hierarchiczna struktura
Generacja dla eksperymentów EDoG:
- Utworzenie BA graph z 1,000 węzłami, parametr m=1
- Przypisanie początkowych 20-wymiarowych random features e_u
- Skorelowanie features ze strukturą grafu (3 iteracje neighborhood aggregation):
- e_u = Σ_{v∈N(u)} e_v
- e_u = e_u / ||e_u||_2
- Generacja binary feature vector: P[x^(i)_u = 1] = sigmoid(e^(i)_u)
- Generacja labels: y_u = 1 if Σ_i x^(i)_u > 0, else 0
Rezultat: ~75% node classification accuracy (niższy niż ER ~80%, prawdopodobnie przez bardziej heterogeniczną strukturę).
Zastosowania
- Modelowanie real-world networks (social, citation, biological)
- Testowanie GNN robustness na realistic graph structures
- Badanie wpływu hubs i power-law distribution na adversarial detection
- Porównanie z random graphs (ER) i real citation networks
Używany w publikacjach
- xu-edog-adversarial-2023 - Synthetic evaluation dataset dla EDoG, wykazał że pipeline osiąga lepszą performance na scale-free graphs (>92% avg AUC) niż na ER graphs (~80%), co pokazuje wykorzystanie strukturalnych właściwości podobnych do real-world networks
Benchmarki
| Model | Metric (Detection AUC) | Score | Typ Ataku | Publikacja |
|---|---|---|---|---|
| EDoG | AUC (avg) | >92% | All attacks | Xu et al. 2023 |
| Katz | AUC (varies) | 26-62% | Varies by attack | Xu et al. 2023 |
| ALD | AUC (varies) | 50-75% | Varies by attack | Xu et al. 2023 |
| Model | Metric (Node Classification) | Score | Publikacja |
|---|---|---|---|
| GCN | Accuracy | ~75% | Xu et al. 2023 |
Uwagi
- Performance EDoG na BA graphs (>92% avg AUC) jest znacząco wyższa niż na ER graphs (~80%), co sugeruje że:
- EDoG skutecznie wykorzystuje strukturalne właściwości scale-free networks
- Hubs i hierarchiczna struktura pomagają w detekcji adversarial edges
- Scale-free structure jest bliższa real-world citation networks (Cora, Citeseer)
- Node classification accuracy (75%) niższa niż ER (80%), prawdopodobnie przez większą heterogeniczność degree distribution
- Parametr m=1 tworzy stosunkowo sparse graph
- Wybrano 2 target nodes: lowest i highest degree dla attack evaluation
- BA graphs lepiej niż ER odzwierciedlają właściwości real citation networks używanych w głównych eksperymentach
- Presence of hubs może wpływać na effectiveness OutlierDetect component (high-degree nodes)
Tagi
dataset synthetic scale-free complex-networks preferential-attachment gnn-robustness power-law