A Novel Approach for Detecting Relationships in Social Networks Using Cellular Automata Based Graph Coloring

Kashani, M.; Shojaedini, S.V.; Gorgin, S.

doi:10.22075/ijnaa.2019.4063

A Novel Approach for Detecting Relationships in Social Networks Using Cellular Automata Based Graph Coloring

Document Type : Research Paper

Authors

M. Kashani

S.V. Shojaedini

S. Gorgin

Department of Electrical Engineering and Information Technology Iranian Research Organization for Science and Technology (IROST), Tehran, Iran

10.22075/ijnaa.2019.4063

Abstract

All the social networks can be modeled as a graph, where each roles as vertex and each relation roles as an edge. The graph can be show as $G = [V;E]$, where $V$ is the set of vertices and $E$ is the set of edges. All social networks can be segmented to $K$ groups, where there are members in each group with same features. In each group each person knows other individuals and is in touch with them. In this study, the main goal is introducing a new approach for detecting these groups and minimizing the number of these groups using a cellular automat algorithm. There are two types of social networks, containing simulated social network and real social network. The results show that the introduced method has a great potential to significantly reduce the number of colors assigned and running time of the program.

Keywords

Social networks

Graph coloring

Cellular automata