| |

Study the Effect on the Number of Choices of the Name in Naming Game

Abstract

The naming games model on complex network have been studied in recent researched. Few research on the impact of the available choose of choice of names for the name game have been conducted. The purpose of this study is to find the relationship of the number of choices for the naming games affect the convergence time of the network.

Introduction

The purpose of this study is to find out the impact of the number of available choice of the name for the agent to negotiate to the hearer on the convergence time. Fully connected network and NW Small-world network will be used as the model of the software simulation for analyzing the effect of number of choice of names for the naming games

The Model

NW Small-World Network is used to evaluate the effect on the number of choice of the naming games. The naming game used in this study is modified from the traditional naming game. The algorithm of the revised naming game is as follows:

1. Construct a fully connected or NW Small-World network
2. Randomly select a connected node in the network as the Speaker.
3. Randomly select a neighbor from the Speaker as the Hearer.
4. The Speaker randomly selected a name from his memory and tells the name to the Hearer.
5. If the hearer already has the same name in his memory, the Speak and Hearer retain the uttered word as the correct name and cancel all other words form their memories.
6. Repeat Step 4 for multiple name negotiation until all the names have been negotiated.
7. If the Speaker do not have sufficient name in the memory, Speaker will pick a name from the vocabulary pool. The available name in the pools is limited.
8. If the Hearer do not has the same name after multiple negotiations, the Hearer adds all the names given by the Speaker to his memory.
9. Repeat Step 2 until a randomly selected name was found in over 50% of the overall nodes.

Simulation and analytical results of collective properties

The NW Small-world network size is 200 and each data point is obtained by averaging over 10 different simulations for each of the network realizations. The available name from the vocabulary pool (V) is 3. Figure 1, Figure 2 and Figure 3 show the convergence times in log scale versus degree of the network.
[pic]
Figure 1
[pic]
Figure 2
[pic]
Figure 3

The convergence time of the naming game when the number of name to be negotiated in each talk is 1, the curve marked “NAME=1”, is almost the same no matter what is the value of V, number of names in the vocabulary pool. When the number of name per talk increased to 2, the convergence time increase greatly when V increased to 5. When V is 3, the network even cannot have a single name populate over 50% of the network node within 90M convergence time.

It shows that the number of vocabularies in the pool for the Speaker to pick to tell to the Hearer has a significant effect on the convergence time, except that only one name is to be “told” in each step. The more choice of the vocabulary, the more difficult to enable the network have a single name to dominate it.

Conclusion

In this study, a software simulation have been designed and implemented to evaluate the complex network property. The number of choices for the Speaker to tell the Hearer plays an important role in the naming games. The more choice of the names to be told to the Hearer, the more complex the process. The effect is minimal when only one name is to be told at a time.

Appendix: Simulation Software

The simulation software is written in MS Visual C++ 2008. The source code with the project files were submitted by email. No additional drivers or header file need. Source Code of the Software Simulation is shown below:

#include
#include
#include
#include

#define MAX_NODE 200
#define MAX_MEMORY 52
#define VOCAB_SIZE 5
#define MAX_TALK 10
#define RG 1
#define NWSW 2 int NAMES_EACH_TALK = 1;

char VOCAB[52] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'x', 'w', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'X', 'W', 'Y', 'Z'};

int Average_Degree[20]; long int Steps[20];

typedef struct Node { int degree; char memory[MAX_MEMORY]; int memory_slot; int neighbour[MAX_NODE-1]; bool memory_empty;
} agent;

agent ER[MAX_NODE];

void ER_Generator(float P); void NWSW_Generator(float P); void Connect(int i, int j); float random (void); void Talking(void); void init_ER (void); int consensus_check(void); void output_data(char *imname); int average_degree(void); void Data_Log(char *filename, int mode);

void Data_Log(char *filename, int mode) { int i=0, j, avg_k=0, k_bar, loop_count=10; long int step=0, step_bar; bool timeout=false;

for(j=0;j