Finding cliques in simulated social networks using graph coloring technique

العناوين الأخرى

اكتشاف المجموعات في الشبكات الاجتماعية الافتراضية باستخدام تقنية تلوين المخططات

مقدم أطروحة جامعية

al-Umari, Muhammad Husayn Ahmad

مشرف أطروحة جامعية

al-Malkawi, Muhammad
Viktorov, Oleg

أعضاء اللجنة

al-Shruf, Fayiz
Murad, Sharifah
al-Sayyid, Rizq

الجامعة

جامعة الشرق الأوسط

الكلية

كلية تكنولوجيا المعلومات

القسم الأكاديمي

قسم علم الحاسوب

دولة الجامعة

الأردن

الدرجة العلمية

ماجستير

تاريخ الدرجة العلمية

2017

الملخص الإنجليزي

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.

التخصصات الرئيسية

تكنولوجيا المعلومات وعلم الحاسوب

الموضوعات

• مواقع التواصل الاجتماعي

عدد الصفحات

70

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-762687