Autoregressive networks with dependent edges

Titel: Autoregressive Networks with Dependent Edges

Auteurs: Jinyuan Chang, Qin Fang, Eric D. Kolaczyk, Peter W. MacDonald, en Qiwei Yao.

---

1. Probleemstelling

Het modelleren van dynamische netwerken waarbij de randen (edges) onderling afhankelijk zijn, is van groot praktisch belang maar technisch uitdagend. In veel real-world netwerken (zoals sociale netwerken, communicatie- of handelsnetwerken) hangt de evolutie van een verbinding tussen twee knopen af van andere randen in het netwerk. Bekende fenomenen die deze afhankelijkheid verklaren zijn:

• Transitiviteit: "De vriend van mijn vriend is ook mijn vriend."
• Graduële heterogeniteit: Populaire knopen hebben meer kans op nieuwe verbindingen ("rich get richer").
• Reciprociteit: Als A naar B communiceert, is de kans groter dat B terug communiceert.

Bestaande modellen kampen met beperkingen:

• Statische modellen (ERGM): Vaak moeilijk te schatten en niet ontworpen voor dynamiek.
• Eenvoudige AR-netwerkmodellen: Veronderstellen vaak dat randen conditioneel onafhankelijk zijn, gegeven hun verleden, en negeren daardoor complexe afhankelijkheden binnen een tijdsstip (zoals transitiviteit).
• Latente variabelenmodellen: Dependentie is impliciet en moeilijk te configureren om specifieke netwerkkenmerken expliciet te modelleren.
• TERGM/SAOM: Hoewel flexibel, zijn ze computationally zwaar en hebben ze beperkte asymptotische theorie, vooral wanneer het aantal knopen ($p$) meegroeit met de steekproefgrootte ($n$).

De kernuitdaging is het ontwikkelen van een model dat expliciete rand-afhankelijkheid toelaat, computationeel efficiënt is, en waarvoor rigoureuze asymptotische theorie geldt in een hoogdimensionale setting ($p \to \infty$).

---

2. Methodologie

A. Het Dependent-Edge AR(m) Kader

De auteurs stellen een nieuw klasse van Autoregressive (AR) netwerken met afhankelijke randen voor.

• Definitie: Gegeven het verleden $\{X_s\}_{s \le t-1}$, zijn de randen $X_{t,ij}$ conditioneel onafhankelijk, maar hun vormings- en opheffingskansen ($\alpha_{t-1,ij}$ en $\beta_{t-1,ij}$) hangen expliciet af van de geschiedenis van andere randen.
• Overgangskansen: De kans dat een rand ontstaat of verdwijnt wordt gemodelleerd via functies $f_{i,j}$ en $g_{i,j}$ die afhankelijkheden zoals transitiviteit en graden kunnen incorporeren.
• Voorbeeldmodellen:
  1. Graduële Heterogeniteit: Randkansen hangen af van de graden van de betrokken knopen en het gemiddelde van de rest van het netwerk.
  2. Persistentie: Randkansen hangen af van de status van de rand in eerdere tijdstippen ($t-2, t-3$).
  3. Transitiviteit: De kans op een nieuwe rand hangt af van het aantal gemeenschappelijke buren (common neighbors) en het aantal disjuncte buren.

B. Schattingsprocedure

Vanwege de hoge dimensionaliteit (het aantal parameters groeit met $p$) lijdt de natuurlijke Maximum Likelihood Schatter (MLE) aan trage convergentie. De auteurs ontwikkelen een tweestapsprocedure:

1. Initiële Schatting (Initial Estimator):

   • Het onderscheid tussen globale parameters (die voor alle randen gelden, bijv. transitiviteitssterkte) en lokale parameters (knop-specifiek, bijv. $\xi_i, \eta_i$) is cruciaal.
   • Er wordt een partiële log-likelihood gebruikt om parameters te schatten.
   • De initiële schatter $\tilde{\theta}$ convergeert, maar met een trage snelheid ($O_p(n^{-1/4})$ of slechter) door de correlatie tussen parameters.

2. Verbeterde Schatting (Improved Estimator via Projectie):

   • Om de impact van de "nuisance parameters" (de andere parameters) te mitigeren, wordt de scorefunctie geprojecteerd op de richting van de parameter van interesse.
   • Dit gebeurt via een geprojekteerde scorefunctie $\hat{f}_t^{(l)}(\theta) = \hat{\phi}_l^T g_t^{(l)}(\theta)$, waarbij $\hat{\phi}_l$ wordt verkregen door een lineair programmeringsprobleem (LP) op te lossen.
   • De uiteindelijke schatter $\hat{\theta}$ wordt gevonden door deze geprojecteerde scorefunctie te minimaliseren, waarbij de andere parameters op hun initiële schatting worden gehouden.

C. Asymptotische Theorie

• Martingaal Verschil Structuur: De auteurs bouwen een martingaal-differentiestructuur op, wat het mogelijk maakt om asymptotische resultaten af te leiden zonder de aanname van stationariteit.
• Verdeling: De limietverdeling van de verbeterde schatter is in het algemeen niet normaal, maar een mengsel van normale verdelingen. Echter, onder mengcondities (mixing conditions) reduceert deze tot een normale verdeling.
• Convergentie: De verbeterde schatter bereikt een snellere convergentiesnelheid ($O_p(n^{-1/2})$) dan de initiële schatter, zelfs wanneer $p$ meegroeit met $n$ (onder bepaalde voorwaarden zoals $p \ll n^{1/2}$).

---

3. Belangrijkste Bijdragen

1. Nieuw Modelleringskader: Introductie van een flexibele AR(m) structuur die expliciete afhankelijkheden tussen randen toelaat, in tegenstelling tot eerdere AR-modellen die alleen edgewise afhankelijkheid toelaten.
2. Hoogdimensionale Asymptotiek: Het ontwikkelen van een theoretisch kader voor netwerken waarbij het aantal knopen $p$ divergeert met de steekproefgrootte $n$, zonder stationariteit aan te nemen.
3. Verbeterde Schattingsalgoritme: Toepassing van projectie-technieken (gebaseerd op Chang et al., 2021, 2023) om de convergentiesnelheid te versnellen en de impact van hoge dimensionaliteit te reduceren.
4. Software Implementatie: Beschikbaarstelling van het R-pakket arnetworks voor simulatie en schatting.
5. Empirische Validatie: Toepassing op real-world data (e-mailinteracties en conferentie-interacties) en uitgebreide simulaties die de superioriteit van het model tonen ten opzichte van bestaande methoden (zoals TERGM en edgewise AR).

---

4. Resultaten

• Simulaties:

  • De verbeterde schatter ($\hat{\theta}$) toont een aanzienlijk lagere fout (Relative Mean Absolute Error) dan de initiële schatter ($\tilde{\theta}$), met name voor de transitiviteitsparameters.
  • De dekkingskans van de 95% betrouwbaarheidsintervallen (op basis van de asymptotische verdeling) ligt dicht bij de nominale waarde, wat de validiteit van de theorie bevestigt.
  • Het model presteert goed zelfs bij grote netwerken ($p=500$).

• Real Data Analyse (E-mailnetwerk):

  • Geanalyseerd op data van een Poolse fabriek (2010).
  • Het model detecteert sterke transitiviteitseffecten: randen vormen zich vaker bij knopenparen met gemeenschappelijke buren.
  • Er is sprake van graden-heterogeniteit: managers hebben een hogere neiging om nieuwe randen te vormen.
  • Modelvergelijking: Het voorgestelde Transitiviteit AR-model presteert beter (laagste BIC) dan een "Global AR" model en een "Edgewise AR" model, en is competitief met een "Edgewise mean" model, maar biedt wel de voordelen van dynamische afhankelijkheid.

• Real Data Analyse (Conferentie):

  • Toepassing op RFID-data van een conferentie. Het model bevestigt transitiviteit en heterogeniteit in face-to-face interacties.

---

5. Betekenis en Impact

Dit werk vult een belangrijke lacune in de literatuur over dynamische netwerken op. Het biedt een brug tussen de flexibiliteit van complexe modellen zoals TERGM/SAOM en de schaalbaarheid en theoretische onderbouwing van autoregressieve modellen.

• Praktische Toepasbaarheid: De methode is toepasbaar op grote, dynamische netwerken waar traditionele methoden falen door computationele complexiteit of gebrek aan convergentie.
• Theoretische Vooruitgang: Het bewijst dat consistente schatting en asymptotische normaliteit mogelijk zijn in hoogdimensionale dynamische netwerken zonder stationariteit aan te nemen, wat een fundamentele stap is in de statistische netwerkanalyse.
• Interpretatie: Het model stelt onderzoekers in staat om specifieke mechanismen (zoals transitiviteit) te kwantificeren en te testen, wat essentieel is voor het begrijpen van de evolutie van sociale, biologische en technologische netwerken.

Kortom, de auteurs presenteren een robuust, schaalbaar en theoretisch onderbouwd raamwerk voor het modelleren van complexe, dynamische netwerken met afhankelijke randen.