Spectral Complexity of Directed Graphs and Application to Structural Decomposition
المؤلفون المشاركون
Mezić, Igor
Fonoberov, Vladimir A.
Fonoberova, Maria
Sahai, Tuhin
المصدر
العدد
المجلد 2019، العدد 2019 (31 ديسمبر/كانون الأول 2019)، ص ص. 1-18، 18ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2019-01-01
دولة النشر
مصر
عدد الصفحات
18
التخصصات الرئيسية
الملخص EN
We introduce a new measure of complexity (called spectral complexity) for directed graphs.
We start with splitting of the directed graph into its recurrent and nonrecurrent parts.
We define the spectral complexity metric in terms of the spectrum of the recurrence matrix (associated with the reccurent part of the graph) and the Wasserstein distance.
We show that the total complexity of the graph can then be defined in terms of the spectral complexity, complexities of individual components, and edge weights.
The essential property of the spectral complexity metric is that it accounts for directed cycles in the graph.
In engineered and software systems, such cycles give rise to subsystem interdependencies and increase risk for unintended consequences through positive feedback loops, instabilities, and infinite execution loops in software.
In addition, we present a structural decomposition technique that identifies such cycles using a spectral technique.
We show that this decomposition complements the well-known spectral decomposition analysis based on the Fiedler vector.
We provide several examples of computation of spectral and total complexities, including the demonstration that the complexity increases monotonically with the average degree of a random graph.
We also provide an example of spectral complexity computation for the architecture of a realistic fixed wing aircraft system.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Mezić, Igor& Fonoberov, Vladimir A.& Fonoberova, Maria& Sahai, Tuhin. 2019. Spectral Complexity of Directed Graphs and Application to Structural Decomposition. Complexity،Vol. 2019, no. 2019, pp.1-18.
https://search.emarefa.net/detail/BIM-1133312
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Mezić, Igor…[et al.]. Spectral Complexity of Directed Graphs and Application to Structural Decomposition. Complexity No. 2019 (2019), pp.1-18.
https://search.emarefa.net/detail/BIM-1133312
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Mezić, Igor& Fonoberov, Vladimir A.& Fonoberova, Maria& Sahai, Tuhin. Spectral Complexity of Directed Graphs and Application to Structural Decomposition. Complexity. 2019. Vol. 2019, no. 2019, pp.1-18.
https://search.emarefa.net/detail/BIM-1133312
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1133312
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر