13. Higher-order Naming Game#

import numpy as np
from scipy import random
import networkx as nx
import pandas as pd
import random
import collections
import matplotlib.pyplot as plt
%matplotlib inline

13.1. Model construction#

#Model constructor
class HigherOrderNamingGame():
    
    def __init__(self, simplices, rule):
        
        #Structure
        self.simplices = simplices
        self.nodes = list({node for simplex in simplices for node in simplex}) 
        self.N = len(self.nodes)
        
        #Time
        self.t = 0
        
        #Rule
        self.rule = rule

    def SetInitialConditions(self, beta, p, n_A, verbose=False):
        
        #Game parameters
        self.beta = beta
        self.p = p
    
        #Opinions of the nodes (vocabularies)
        self.opinions = {}
        
        #Generating committed agents
        N_p = int(self.N*self.p) #number of committed agents
        #Randomly picking N_p committed agents
        committed = random.sample(self.nodes, N_p)
        #Setting up a committed dictionary
        #self.is_committed = {n:False for n in self.nodes}
        for n in self.nodes:
            if n in committed:
                #self.is_committed[n]=True
                #Assigning opinion "A" to committed agents
                self.opinions[n]=frozenset(["A"])
        
        #Calculating the number of agents holding n_A (not committed) from the density in input
        N_A = int(self.N*n_A)
        N_B = self.N-N_A-N_p
        #Creating a list of opinions to assign
        opinions_to_assign = ['A']*N_A + ['B']*N_B
        #Shuffling them
        random.shuffle(opinions_to_assign)
        #Agents left to be matched with opinions
        noncommitted = set(self.nodes) - set(committed)
        for n, o in zip(noncommitted, opinions_to_assign):
            self.opinions[n]=set(o)
            
        if verbose: print('Setup Done.', self.N, 'nodes,', "N_A:", N_A, "N_B:", N_B, "N_p:", N_p) 
    
    def AgreeOnSimplex(self, simplex, said_word):
        
        #Updating the simplex on the agreed word 
        for n in simplex:
            try: #There are also committed minorities which have frozensets!
                self.opinions[n].clear()
                self.opinions[n].add(said_word)
            except AttributeError: #It was committed
                pass

    def ListenersLearnWord(self, listeners, said_word):
        
        #Looping through the listeners
        for listener in listeners:
            try: #Trying to learn...
                self.opinions[listener].add(said_word)
            except AttributeError: #It was committed
                pass
                
    def play_on_simplex(self, simplex):
        
        #Selecting speaker and listeners at random
        random.shuffle(simplex)
        speaker = simplex[0]
        listeners = simplex[1:]
        
        #Selecting a random word to be said
        said_word = random.choice(list(self.opinions[speaker]))
        words_of_listeners = [self.opinions[listener] for listener in listeners]
        
        #Using the rule to get the words of listeners to be used for the agreement
        if self.rule=='union': 
            words_of_listeners_by_rule = set.union(*[set(w) for w in words_of_listeners])
        elif self.rule=='intersection':    
            words_of_listeners_by_rule = set.intersection(*[set(w) for w in words_of_listeners])
        
        #Trying to agree based on the rule and the communication efficiency beta
        if (said_word in words_of_listeners_by_rule) and (random.random() <= self.beta):
            self.AgreeOnSimplex(simplex, said_word)
        else: #No agreement, but the said word is learned by the listeners
            self.ListenersLearnWord(listeners, said_word)
            
    def get_densities(self):
        single_opinion_counter = collections.Counter([list(opinions)[0] for opinions in self.opinions.values() if len(opinions)==1])
        n_Ap = single_opinion_counter["A"]/self.N
        n_B = single_opinion_counter["B"]/self.N
        n_AB = 1-n_Ap-n_B
        return n_Ap, n_B, n_AB

    def run(self, path, t_max=100, check_every=10, print_every=1):
        
        self.t_max = t_max
        
        #Opening file to save densities results
        densities_path = path + 'HONG_densities_N%i_beta%.4f_p%.2f.csv'%(self.N, self.beta, self.p)
        f = open(densities_path,'w')
        f.write('time,n_A+p,n_B,n_AB\n')
        
        while self.t <= self.t_max:
            self.t += 1
            if self.t%print_every==0: print('t=%i'%self.t)
                
            ######### THIS IS FOR PLAYING ALWAYS ON ALL SIMPLICES AT EACH TIME #########
            #Reshuffling the sequence of simplices
            #random.shuffle(self.simplices)
            
            #Looping over each simplex and playing
            #for simplex in self.simplices:
                #self.play_on_simplex(simplex)
            ############################################################################
            
            #Playing on a random simplex 
            simplex = random.choice(self.simplices)
            self.play_on_simplex(simplex)
                
            #Storing the values every check_every time steps:
            if self.t%check_every==0:
                n_Ap, n_B, n_AB = self.get_densities()
                line = "%i,%.3f,%.3f,%.3f\n"%(self.t, n_Ap, n_B, n_AB)
                f.write(line)
                
                #Also checking if we reached the absorbing state:
                if n_Ap==1 or n_B==1:
                    f.close()   
                    print('DONE! Reached the absorbing state.')
                    return None
                
        f.close()    
        print('DONE! Run out of time...')

13.2. Testing it on a small toy hypergraph#

simplices = [[1,2,3],[2,3,5],[6,1,7]]
rule = 'intersection'

beta = 0.3
p = 0.01
n_A = 0

output_path = 'results/'
t_max = 1000
check_every = 1

HONG = HigherOrderNamingGame(simplices, rule)
HONG.SetInitialConditions(beta=beta, p=p, n_A=n_A, verbose=True)
HONG.run(output_path, t_max, check_every)
Setup Done. 6 nodes, N_A: 0 N_B: 6 N_p: 0
t=1
DONE! Reached the absorbing state.
df = pd.read_csv('results/HONG_densities_N6_beta0.3000_p0.40.csv')
df.plot(x='time')
<AxesSubplot:xlabel='time'>
../_images/d668b63fee62875fc5617ef93f6500edc223affac42120dd2e4c8d3885620ba8.png

13.3. Running on an homogeneous mixing 2-hypergraph#

from itertools import combinations

def HomMix2HG(N, k=2):
    nodes = range(N)
    simplices = list(combinations(nodes, k+1))
    #These are tuples, so I'll convert them to lists
    simplices = [list(simplex) for simplex in simplices]
    return simplices
N = 500
simplices = HomMix2HG(N)
rule = 'union'

beta = 0.7
p = 0.08
n_A = 0

output_path = 'results/%s_'%rule
t_max = 1e5
check_every = 100
print_every=100

HONG = HigherOrderNamingGame(simplices, rule)
HONG.SetInitialConditions(beta=beta, p=p, n_A=n_A, verbose=True)
HONG.run(output_path, t_max, check_every, print_every)
Setup Done. 500 nodes, N_A: 0 N_B: 460 N_p: 40
t=100
t=200
t=300
t=400
t=500
t=600
t=700
t=800
t=900
t=1000
t=1100
t=1200
t=1300
t=1400
t=1500
t=1600
t=1700
t=1800
t=1900
t=2000
t=2100
t=2200
t=2300
t=2400
t=2500
t=2600
t=2700
t=2800
t=2900
t=3000
t=3100
t=3200
t=3300
t=3400
t=3500
t=3600
t=3700
t=3800
t=3900
t=4000
t=4100
t=4200
t=4300
t=4400
t=4500
t=4600
t=4700
t=4800
t=4900
t=5000
t=5100
t=5200
t=5300
t=5400
t=5500
t=5600
t=5700
t=5800
t=5900
t=6000
t=6100
t=6200
t=6300
t=6400
t=6500
t=6600
t=6700
t=6800
t=6900
t=7000
t=7100
t=7200
t=7300
t=7400
t=7500
t=7600
t=7700
t=7800
t=7900
t=8000
t=8100
t=8200
t=8300
t=8400
t=8500
t=8600
t=8700
t=8800
t=8900
t=9000
t=9100
t=9200
t=9300
t=9400
t=9500
t=9600
t=9700
t=9800
t=9900
t=10000
t=10100
t=10200
t=10300
t=10400
t=10500
t=10600
DONE! Reached the absorbing state.
N = 500
rule = 'union'
beta = 0.7
p = 0.08

df = pd.read_csv('results/%s_HONG_densities_N%i_beta%.4f_p%.2f.csv'%(rule,N, beta, p))
df.plot(x='time')
<AxesSubplot:xlabel='time'>
../_images/a228654277b626054eca6f4317aaf50503da4427a8615f3c56b0951717357a87.png
## full code is available here: https://github.com/iaciac/higher-order-NG