Thesis (Ph.D)-Cairo University, 2023.

Bibliography: pages 96-111.

Community search is a fundamental problem in graph analysis. In many ap-
plications, network nodes have specific properties that are essential for mak-
ing sense of communities. In these networks, attributes are associated with
nodes to capture their properties. Community influence is a key property of
the community that can be employed to sort the communities in a network
based on the relevance/importance of certain attributes. Most of the pre-
viously introduced community search algorithms over attributed networks
neglected the community influence. However, certain applications require
finding the top-r influential communities in the network. The objective of
this thesis is to identify the top-r communities with the highest influence val-
ues while satisfying the topology constraints.
In this thesis, different factors for measuring the influence are discussed.
In addition, two Influential Attributed Community (In f ACom) approaches
based on the concept of k-clique are introduced. The first approach, Whole −
In f ACom, is a sequential technique that consists of two main modules: the
graph summarization module and the community search module. Whole −
In f ACom is appropriate for small graphs and deals with the graph as a
whole. Whole − In f ACom uses three query processing methods for retriev-
ing the top-r k-influential communities: BasicExact, EnhancedExact, and
Approximate. The second approach is Decomposed − In f ACom which is a
parallel technique that employs a graph partitioning technique to improve
the performance of the graph summarization module as well as the com-
munity search module. This approach provides great speed in building the
summary graph as well as retrieving the top-r influential communities. In
addition, different algorithms for managing dynamic networks where edges
and/or attributes could be inserted or deleted are proposed. Moreover, to
deal with the problem of the lack of information as the graph is partially la-
beled, a semi-supervised model named Influential Attributed Communities
via Graph Convolutional Network (In f ACom − GCN) is presented.
The proposed algorithms are evaluated on different real datasets. Ac-
cording to the experimental results, the summarization technique reduces
the size of the graph by about half. Furthermore, the results demonstrate
that the proposed algorithms EnhancedExact and Approximate outperform
state-of-the-art approaches Incremental Time efficient (Inc − T), Incremental
Space efficient (Inc − S), Exact, and 2-Approximation (AppInc) in terms of
both efficiency and effectiveness. The efficiency of the EnhancedExact algo-
rithm is at least 7 times faster than the Inc − S algorithm, at least 4.5 times
faster than the Inc − T algorithm, and at least 2 times faster than the AppInc
algorithm. The results show that the Approximate algorithm is at least 10
times faster than the Inc − S algorithm, 6.4 times faster than the Inc − T al-
gorithm, and 3 times faster than the AppInc algorithm. Furthermore, the
results demonstrate that the proposed algorithms return cohesive communi-
ties with smaller diameters than all previous approaches. Finally, the exper-
iments show that the In f ACom − GCN outperforms GCN–FullBatch, GAT,
and GraphSAGE.

البحث عن المجتمعات تعتبر مشكلة أساسية في تحليل الرسم البياني. في العديد من التطبيقات، تحتوي الشبكات على عقد بها خصائص محددة ضرورية لفهم المجتمعات. في هذه الشبكات، ترتبط بعض السمات بالعقد وصف خصائصها.
تأثير المجتمع هو خاصية رئيسية للمجتمع يمكن توظيفها لترتيب المجتمعات في الشبكة بناءً على أهمية سمات معينة. معظم خوارزميات البحث المجتمعي المقدمة سابقًا عبر الشبكات ذات السمات أهملت تأثير المجتمع. ومع ذلك، تتطلب بعض التطبيقات العثور على أعلى المجتمعات تأثيرا في الشبكات. الهدف من هذه الرسالة هو تحديد المجتمعات ذات التأثير الاعلى مع الاخذ في الاعتبار الشروط المطلوبة في بنيه الشبكة.
في هذه الأطروحة، تم تقديم مقياس جديد لقياس تأثير المجتمعات في الشبكات مع الاخذ في الاعتبار عدة عوامل مختلفة. بالإضافة إلى ذلك، تم تقديم نموذجان مختلفين للبحث عن المجتمعات المؤثرة في الشبكات ذات السمات.
النموذج الأول هو أسلوب تسلسلي يتكون من وحدتين رئيسيتين هما: وحدة تلخيص الرسم البياني ووحدة البحث عن المجتمعات. هذا النموذج مناسب للشبكات صغيرة الحجم حيث يتم التعامل مع الشبكة كوحدة واحده حيث يتم البحث عن المجتمعات ذات التأثير الأعلى في الشبكة ذات السمات. هذا النموذج يستند إلى ثلاث طرق لمعالجة الاستعلام لاسترداد المجتمعات ذات التأثير الأعلى وفقا لبنود الاستعلام. النموذج الثاني هو تقنية موازية تعتمد على تقسيم الرسم البياني إلى أجزاء أصغر والعمل بالتوازي عليها وذلك لتحسين أداء وحدة تلخيص الرسم البياني بالإضافة إلى وحدة البحث عن المجتمعات. يوفر هذا النهج سرعة كبيرة في بناء الرسم البياني الموجز وكذلك استرداد المجتمعات ذات التأثير الأعلى. علاوة على ذلك، للتعامل مع مشكلة نقص المعلومات حيث تم تسمية الرسم البياني جزئيًا، تم تقديم نموذج شبه خاضع للإشراف يسمى المجتمعات المنسوبة المؤثرة عبر الشبكة التلافيفية للرسم البياني.
تم تقييم الخوارزميات المقترحة على مجموعات بيانات حقيقية مختلفة في الحجم. وفقًا للنتائج التجريبية، تقلل تقنية تلخيص حجم الرسم البياني بمقدار النصف تقريبًا. علاوة على ذلك، توضح النتائج أن الخوارزميات المقترحة تتفوق على أحدث الأساليب من حيث الكفاءة والفاعلية.

Issued also as CD

Text in English and abstract in Arabic & English.