Finding cliques in simulated social networks using graph coloring technique
Other Title(s)
اكتشاف المجموعات في الشبكات الاجتماعية الافتراضية باستخدام تقنية تلوين المخططات
Dissertant
al-Umari, Muhammad Husayn Ahmad
Thesis advisor
al-Malkawi, Muhammad
Viktorov, Oleg
Comitee Members
al-Shruf, Fayiz
Murad, Sharifah
al-Sayyid, Rizq
University
Middle East University
Faculty
Faculty of Information Technology
Department
Computer Science Department
University Country
Jordan
Degree
Master
Degree Date
2017
English Abstract
In this thesis, the problem of finding cliques has addressed in large graphs such as social networks.
The problem of finding all cliques in a graph is known to be NP problem.
A new heuristic approach for finding cliques has provided.
The new approach represents a graph coloring technique which is based on the using of Largest Degree Coloring algorithm, which colors a graph starting with the largest degree node in a particular graph.
This proposed approach follows the largest cliques in a graph and moves to finding smaller cliques.
The proposed approach with the algorithm for finding cliques in heuristic method and the exhaustive search algorithm has used as a reference.
A lot of experiments has been conducted in this study on different data sets, 72 experiments of them by applying the three algorithms on variants data sets generated by our java program, and five experiments data set taken from standard DIMACS benchmark and last data set consist of simulated social networks, in range between 10000 nodes and 50000 nodes.
hopefully to apply the proposed approach in real social networks, knowing that the exhaustive search may take relatively large time.
the new approach based on graph coloring has achieved better complexity and detectability of cliques.
However, the results of a proposed approach have shown that there is enhancement in time complexity than other two approaches that used in comparison to proposed algorithm and the number of detected cliques.
Main Subjects
Information Technology and Computer Science
Topics
No. of Pages
70
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : Literature review.
Chapter Three : Methodology.
Chapter Four : Peformance analysis and results.
Chapter Five : Conclusions and future works.
References.
American Psychological Association (APA)
al-Umari, Muhammad Husayn Ahmad. (2017). Finding cliques in simulated social networks using graph coloring technique. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-762687
Modern Language Association (MLA)
al-Umari, Muhammad Husayn Ahmad. Finding cliques in simulated social networks using graph coloring technique. (Master's theses Theses and Dissertations Master). Middle East University. (2017).
https://search.emarefa.net/detail/BIM-762687
American Medical Association (AMA)
al-Umari, Muhammad Husayn Ahmad. (2017). Finding cliques in simulated social networks using graph coloring technique. (Master's theses Theses and Dissertations Master). Middle East University, Jordan
https://search.emarefa.net/detail/BIM-762687
Language
English
Data Type
Arab Theses
Record ID
BIM-762687
