DOI: https://doi.org/10.1038/s41598-026-41731-9
PMID: https://pubmed.ncbi.nlm.nih.gov/41766019
تاريخ النشر: 2026-03-01
المؤلف: Fang Yang وآخرون
الموضوع الرئيسي: تقنيات تحليل الشبكات المعقدة
نظرة عامة
أصبح مشكلة تعظيم التأثير (IM) ذات صلة متزايدة في كل من السياقات الصناعية والأكاديمية، خاصة بسبب النمو السريع لبيانات الشبكة وتعقيد سيناريوهات التطبيق. لقد واجهت خوارزميات التقريب التقليدية تحديات مثل الضمانات النظرية غير الكافية، والأداء غير الأمثل، والتكاليف الحسابية العالية. بينما تم تطوير أساليب التعلم العميق الحديثة، فإنها غالبًا ما تفتقر إلى القابلية للتعميم في الشبكات الكبيرة غير المتجانسة.
لمعالجة هذه القيود، يقدم هذا البحث MaDGNN، وهو إطار عمل للتعلم المعزز العميق مصمم لمعالجة مشكلة IM بشكل فعال في الشبكات الاجتماعية الكبيرة باستخدام الشبكات العصبية الرسومية وتقنيات التعلم المعزز. تُظهر الخوارزمية المقترحة تحسينات كبيرة مقارنة بالطرق الأساسية في تجارب تجريبية واسعة النطاق عبر مجموعات بيانات العالم الحقيقي المختلفة. ومن الجدير بالذكر أن MaDGNN يظهر قابلية قوية للتوسع، حيث يعمل بشكل جيد على الرسوم البيانية الأكبر حتى عند تدريبه على الرسوم البيانية الأصغر، مما يعزز قابليته للتطبيق عبر أنواع الشبكات المختلفة.
مقدمة
تسلط مقدمة هذه الورقة الضوء على أهمية الشبكات الاجتماعية عبر الإنترنت (OSNs) كمنصات للتواصل ونشر المعلومات، مع التأكيد على قيمتها الاقتصادية من خلال تطبيقات مثل أنظمة التوصية والتسويق عبر الإنترنت. لقد حصلت مشكلة تعظيم التأثير (IM)، التي تم صياغتها بواسطة كيمبي وآخرين كتحدي تحسين توافقي، على اهتمام بحثي واسع بسبب طبيعتها NP-hard وتعقيدات تقدير انتشار التأثير تحت نماذج الانهيار المستقل (IC) والعتبة الخطية (LT). على الرغم من أن الخوارزميات الجشعة يمكن أن تحقق نسبة تقريب قدرها \( (1 – 1/e) \)، إلا أنها تواجه تحديات في قابلية التوسع، خاصة في الشبكات الكبيرة، مما أدى إلى تطوير تقنيات أخذ عينات التأثير العكسي (RIS) والخوارزميات المستندة إلى RIS، التي لا تزال تواجه صعوبات في الحمل الحسابي.
استجابةً لهذه القيود، تقدم الورقة MaDGNN، وهو إطار عمل جديد للتعلم المعزز العميق (DRL) مصمم لمشكلة IM في الشبكات الاجتماعية الكبيرة. يتميز MaDGNN بآلية تحسين مبتكرة “الإدراك-القرار”، التي تتضمن شبكة عصبية رسومية (GNN) مدركة للانهيار تلتقط الميزات الطوبولوجية عالية الترتيب وتأثيرات الانهيار، إلى جانب آلية تعلم معزز من نوع مونشهاوزن لتعزيز استقرار السياسة وقدرات الاستكشاف. يدعي المؤلفون أن MaDGNN يمكنه تقريب التأثير الأقصى المتوقع بشكل فعال كدالة قيمة معلمة ويقدمون نتائج تجريبية واسعة تظهر تفوقه وفعاليته عبر مجموعات بيانات العالم الحقيقي المختلفة. تم هيكلة الورقة لتتبع المقدمة مع النتائج التجريبية الرئيسية، ومناقشة النتائج، وقسم طرق مفصل لضمان إمكانية إعادة الإنتاج.
طرق
تحدد قسم الطرق إعداد التجارب ونتائج الدراسة. يوضح إعداد التجارب الظروف والمواد المحددة المستخدمة، بما في ذلك أي أجهزة أو تقنيات تم استخدامها لجمع البيانات. ويؤكد على أهمية التحكم في المتغيرات لضمان موثوقية النتائج.
في نتائج التجارب، يتم تحليل البيانات التي تم جمعها وعرضها، مع تسليط الضوء على النتائج الرئيسية والاتجاهات التي لوحظت خلال التجارب. قد يتم استخدام طرق إحصائية للتحقق من دلالة النتائج، مما يوفر فهمًا واضحًا لتداعيات النتائج ضمن سياق أهداف البحث. بشكل عام، يخدم هذا القسم في تأسيس الصرامة وإمكانية إعادة إنتاج التجارب التي تم إجراؤها.
نتائج
في هذا القسم، يقدم المؤلفون سلسلة من التجارب التي تهدف إلى التحقق من أداء النموذج المقترح عبر مجموعات بيانات مختلفة. تم تنفيذ التجارب على جهاز كمبيوتر شخصي مزود بمعالج Intel Core i7-10700 (2.90GHz، 8 نوى)، وذاكرة RAM سعة 16 جيجابايت، وبطاقة رسومات NVIDIA GeForce GTX 1660 SUPER، جميعها تعمل تحت نظام Windows 10.
تعتبر النتائج التي تم الحصول عليها من هذه التجارب حاسمة لتقييم فعالية النموذج وقوته، على الرغم من عدم تفصيل مقاييس الأداء المحددة والتحليلات المقارنة مع النماذج الأساسية في هذا الاقتباس. ستساهم النتائج من هذه التجارب في فهم شامل لقدرات النموذج في التطبيقات العملية.
مناقشة
في هذا القسم، يناقش المؤلفون تقييم أداء طريقتهم المقترحة، MaDGNN، لتعظيم التأثير في الشبكات الاجتماعية. تستخدم الدراسة ثمانية مجموعات بيانات من الشبكات الاجتماعية الواقعية وتستخدم 20 رسمًا عشوائيًا من رسومات إردوش-ريني لتدريب النموذج. يتم استخدام نموذج الانهيار المستقل (IC) بشكل أساسي للانتشار، مع تعيين أوزان الحواف إلى \( \frac{1}{\text{deg}_{\text{in}}(v)} \). يقارن المؤلفون MaDGNN ضد عدة طرق متقدمة، بما في ذلك ToupleGDD و S2V-DQN و CELF-deepis وخوارزمية IMM، عبر مجموعات بيانات متعددة. تشير النتائج إلى أن MaDGNN يحقق باستمرار أعلى انتشار للتأثير مع الحفاظ على كفاءة زمن التشغيل التنافسية، متفوقًا بشكل خاص على S2V-DQN و CELF-deepis.
تسلط المناقشة أيضًا الضوء على قابلية MaDGNN للتكيف مع نماذج الانتشار المختلفة، مثل نموذج العتبة الخطية (LT)، من خلال تعديل دالة المكافأة. يذكر المؤلفون أن أداء MaDGNN يبقى قويًا عبر احتمالات انتشار مختلفة، مما يظهر قدرته على التعميم. علاوة على ذلك، يقومون بإجراء دراسة استئصالية لتقييم تأثير تحسينات مختلفة، بما في ذلك استخدام Munchausen-DQN والتضمينات الأولية من GraphSAGE، والتي تحسن بشكل كبير انتشار التأثير دون تكبد تكاليف زمن تشغيل كبيرة. تشير النتائج إلى أن MaDGNN لا يحدد فقط معيارًا جديدًا لتعظيم التأثير، ولكن أيضًا يفتح آفاقًا للبحث المستقبلي في تحسين الشبكات ودمج التعلم المعزز مع الأساليب القائمة على الرسوم البيانية.
DOI: https://doi.org/10.1038/s41598-026-41731-9
PMID: https://pubmed.ncbi.nlm.nih.gov/41766019
Publication Date: 2026-03-01
Author(s): Fang Yang et al.
Primary Topic: Complex Network Analysis Techniques
Overview
The Influence Maximization (IM) problem has become increasingly relevant in both industrial and academic contexts, particularly due to the rapid growth of network data and the complexity of application scenarios. Traditional approximation algorithms have struggled with challenges such as inadequate theoretical guarantees, suboptimal performance, and high computational costs. While recent deep learning approaches have been developed, they often lack generalizability in heterogeneous large-scale networks.
To address these limitations, this paper presents MaDGNN, a Deep Reinforcement Learning framework designed to effectively tackle the IM problem in large-scale social networks using graph neural networks and reinforcement learning techniques. The proposed algorithm demonstrates significant improvements over baseline methods in extensive empirical experiments across various real-world datasets. Notably, MaDGNN shows strong scalability, performing well on larger graphs even when trained on smaller ones, thereby enhancing its applicability across different network types.
Introduction
The introduction of this paper highlights the significance of Online Social Networks (OSNs) as platforms for communication and information dissemination, emphasizing their economic value through applications like recommendation systems and online marketing. The Influence Maximization (IM) problem, formalized by Kempe et al. as a combinatorial optimization challenge, has garnered extensive research attention due to its NP-hard nature and the complexities of estimating influence spread under the independent cascade (IC) and linear threshold (LT) models. Although greedy algorithms can achieve an approximation ratio of \( (1 – 1/e) \), they face challenges in scalability, particularly in large networks, leading to the development of Reverse Influence Sampling (RIS) techniques and subsequent RIS-based algorithms, which still struggle with computational overhead.
In response to these limitations, the paper introduces MaDGNN, a novel Deep Reinforcement Learning (DRL) framework designed for the IM problem in large-scale social networks. MaDGNN features an innovative “Perception-Decision” optimization mechanism, incorporating a Cascade-aware Graph Neural Network (GNN) that captures high-order topological features and cascade effects, alongside a Munchausen Reinforcement Learning mechanism to enhance policy stability and exploration capabilities. The authors claim that MaDGNN can effectively approximate the expected maximum influence as a parameterized value function and present extensive experimental results demonstrating its superiority and effectiveness across various real-world datasets. The paper is structured to follow the introduction with key experimental findings, a discussion of results, and a detailed methods section to ensure reproducibility.
Methods
The section on Methods outlines the experimental setup and results of the study. The experimental setup details the specific conditions and materials used, including any apparatus or technology employed to gather data. It emphasizes the importance of controlling variables to ensure the reliability of the findings.
In the experimental results, the data collected is analyzed and presented, highlighting key outcomes and trends observed during the experiments. Statistical methods may be employed to validate the significance of the results, providing a clear understanding of the implications of the findings within the context of the research objectives. Overall, this section serves to establish the rigor and reproducibility of the experiments conducted.
Results
In this section, the authors present a series of experiments aimed at validating the performance of the proposed model across various datasets. The experiments were executed on a personal computer equipped with an Intel Core i7-10700 CPU (2.90GHz, 8 cores), 16GB of RAM, and an NVIDIA GeForce GTX 1660 SUPER graphics card, all operating under Windows 10.
The results obtained from these experiments are crucial for assessing the model’s effectiveness and robustness, although specific performance metrics and comparative analyses with baseline models are not detailed in this excerpt. The findings from these experiments will contribute to a comprehensive understanding of the model’s capabilities in practical applications.
Discussion
In this section, the authors discuss the performance evaluation of their proposed method, MaDGNN, for influence maximization in social networks. The study utilizes eight real-world social network datasets and employs 20 random Erdős-Rényi graphs for model training. The Independent Cascade (IC) model is primarily used for diffusion, with edge weights set to \( \frac{1}{\text{deg}_{\text{in}}(v)} \). The authors compare MaDGNN against several state-of-the-art methods, including ToupleGDD, S2V-DQN, CELF-deepis, and the IMM algorithm, across multiple datasets. Results indicate that MaDGNN consistently achieves the highest influence spread while maintaining competitive runtime efficiency, particularly outperforming S2V-DQN and CELF-deepis.
The discussion also highlights the adaptability of MaDGNN to different diffusion models, such as the Linear Threshold (LT) model, by modifying the reward function. The authors report that MaDGNN’s performance remains robust across varying propagation probabilities, demonstrating its generalization ability. Furthermore, they conduct an ablation study to assess the impact of various enhancements, including the use of Munchausen-DQN and initial embeddings from GraphSAGE, which significantly improve influence spread without incurring substantial runtime costs. The findings suggest that MaDGNN not only sets a new benchmark for influence maximization but also opens avenues for future research in network optimization and the integration of reinforcement learning with graph-based approaches.