The Genetic Algorithm as a General Diffusion Model for Social Networks

Mayank Lahiri, Manuel CebriánAAAI 2010 · DOI

Abstract

This paper proposes a unified framework for modeling the spread of information, diseases, or products through social networks by reframing the process as a Genetic Algorithm (GA). By treating social interactions as "crossover" events and information as "chromosomes," the authors demonstrate that many classic diffusion models are special cases of this GA-based approach. Empirical analysis of the Enron email corpus reveals a phenomenon of "information elitism," where network structure facilitates significant stratification in information value that standard network metrics fail to predict.

Introduction

Traditional diffusion models, such as the Independent Cascade model, often treat information as a simple binary state. However, real-world information exchange is complex: ideas can be combined, some are more valuable than others, and synergy between different pieces of information can occur. The authors identify a need for a flexible framework that models these non-linear interactions while remaining mathematically grounded in existing theory. They introduce the GA Diffusion Model (GADM) to bridge this gap.

Methodology: The GA Diffusion Model (GADM)

The GADM maps social dynamics to the mechanics of a Genetic Algorithm through four primary components:

  1. Individuals as Chromosomes: Each node in a social network is represented by a binary string (a chromosome).
  2. Interaction as Crossover: When two nodes interact (represented by an edge), they perform a "crossover" operation, swapping segments of their binary strings to simulate the exchange of ideas.
  3. Value via HDFs: Holland’s Hyperplane-Defined Functions (HDFs) assign scores to specific patterns (schemata) within the binary string, allowing for complex valuation where certain combinations of information are worth more than others.
  4. Selection: If the resulting "offspring" string has a higher score than the parent's original string, the individual adopts the new information.

Mathematical proofs provided in the paper show that by adjusting the HDF and string length, the GADM can perfectly replicate standard models like the Independent Cascade and Competing Processes models.

Empirical Analysis: The Enron Corpus

To test the model in a real-world setting, the authors applied GADM to the Enron email dataset, comprising over 1.3 million timestamped emails between approximately 84,000 addresses. By running thousands of simulations with randomized starting information, they tracked the accumulation of "information value," measured as the Average Normalized Objective (ANO).

Information Stratification and Elitism

The simulations revealed a clear shift from a uniform initial state to a highly stratified final distribution. While most individuals started with near-zero information value, the final state showed a small "elite" group of nodes consistently outperforming the rest of the network. The top-performing individual reached an average of 92% of the maximum possible information value, while the median remained significantly lower.

Comparison of initial and final distributions of Average Normalized Objective (ANO) in the Enron network, showing the emergence of information stratification.

The Failure of Simple Network Metrics

One of the paper's most surprising findings is that this "information elitism" is not easily explained by standard network statistics. Having a high number of connections (In-Degree) or being active in the network for a long duration (FirstSeen) showed very low correlation with an individual's final information value.

Correlation matrix showing the weak relationship between final information value (ANO) and standard network metrics like In-Degree and Out-Degree.

This suggests that "information wealth" is determined by subtle structural properties of the network rather than simple popularity or longevity. Your position in the network determines your potential for information gain, regardless of your initial knowledge.

Conclusion and Future Work

The GADM provides a powerful, unifying lens for studying social diffusion. While the current model uses a canonical GA, the authors suggest future iterations could include mutation to model spontaneous innovation or Genetic Programming to evolve models that match specific real-world events, such as viral Twitter hashtags. Incorporating node metadata, such as job titles or expertise, could further refine our understanding of how personal traits interact with network structure to facilitate information flow.

Summary updated

BibTeX
@inproceedings{lahiri2010genetic,
  author = {Mayank Lahiri and Manuel Cebrián},
  title = {{The Genetic Algorithm as a General Diffusion Model for Social Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7677},
}

Loading related content...

Figure