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

Document Type : Research Paper


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


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 signi cantly reduce the number of colors assigned
and running time of the program.