Статья

Название статьи КЛАСТЕРИЗАЦИЯ ОРИЕНТИРОВАННЫХ ВЗВЕШЕННЫХ ЗНАКОВЫХ ГРАФОВ НА ОСНОВЕ ФУНКЦИОНАЛА ПОТЕНЦИАЛЬНОЙ ЭНЕРГИИ УПРУГОЙ ДЕФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ КОГНИТИВНЫХ МОДЕЛЕЙ
Автор А. Н. Целых, В. С. Васильев, Л. А. Целых
Рубрика РАЗДЕЛ I. МЕТОДЫ И АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ
Месяц, год 03, 2018
Индекс УДК 004.891.2
DOI
Аннотация Предлагается новый подход к кластеризации на основе модели разделения вершин на группы по признаку более высокой потенциальной энергии ребер внутри групп, чем между ними. Этот метод реализуется посредством минимизации функционала потенциальной энергии упругой деформации для ориентированных взвешенных знаковых графов. Существующие структуры в матрице смежности графа выражаются в ее структурированности. Поиск наилучшего упорядочения вершин графа производится посредством процесса оптимизации в пространстве действительных чисел, что неизбежно отображается на множество перестановок индексов вершин. Метод разрабатывался для сетей, представляющих взаимоотношения в экономических системах. Эти взаимоотношения представлены разнородными факторами и причинно-следственными связями между ними. Система объектов и их взаимоотношения представлены в виде нечеткой когнитивной карты, которая, по сути, является ориентированным взвешенным знаковым графом. К этому графу и применяются методы кластеризации. Новизна подхода заключается в том, что решение задачи кластеризации находится как решение задачи оптимизации функции многих переменных (функционалов). Предложенный метод использует механистическую аналогию, которая является частным случаем метрических представлений, что обеспечивает выпуклость задачи. Данный подход позволяет конструировать различные функционалы с понятной интерпретацией и предсказуемостью процесса минимизации. Работа алгоритма заключается в нахождении нумерации вершин графа, при которой достигается наименьшее значение функционала. На этой нумерации компоненты градиента функционала используются для определения границ кластеров. Критерием отнесения вершин к одному сообществу является близость индексов и одинаковые знаки градиента. Эти критерии являются четко формализуемыми. Предлагаемый алгоритм относит вершины к тому или иному кластеру и, одновременно, определяет порядок вершин в кластере. Этот порядок отражает степень распределение вершин по соотношению внутрикластерной энергии и внекластерной энергии связей. Иерархическая структура графа выявляется путем рекурсивного применения предлагаемого алгоритма внутри каждого кластера, игнорируя межкластерные связи. Применяемый в алгоритме кластеризации функционал потенциальной энергии упругой деформации отражает причинно-следственный характер взаимоотношений между факторами в социально-экономической системе. Минимизация функционала происходит монотонно и не требует вмешательства пользователя. Алгоритм является вычислительно эффективным.

Скачать в PDF

Ключевые слова Кластеризация; функционал упругой деформации; ориентированный взвешенный граф; оптимизационные методы; когнитивные карты.
Библиографический список 1. Biscarri F., Monedero I., García A., Guerrero J. and Leon C. Electricity clustering framework for automatic classification of customer loads, Expert Systems With Applications, 2017,
Vol. 86, pp. 54-63.
2. Tsai C.-F., Hu Y.-H. and Lu Y.-H. Customer segmentation issues and strategies for an automobile dealership with two clustering techniques, Expert System, 2015, Vol. 32, No. 1,
pp. 65-76.
3. Cruz A.M. Evaluating record history of medical devices using association discovery and clustering techniques, Expert Systems with Applications, 2013, Vol. 40 (13), pp. 5292-5305.
4. Dias J.G. and Ramos S.B. Dynamic clustering of energy markets: An extended hidden markov approach," Expert Systems with Applications, 2014, Vol. 41 (17), pp. 7722-7729.
5. Lorentz H., Hilmola O., Malmsten J. and Srai J.S. Cluster analysis application for understanding SME manufacturing strategies, Expert Systems with Applications, 2016,
Vol. 66, pp. 176-188.
6. Kosko B. Fuzzy cognitive maps, Int. Journal man-machine Studies, 1986, Vol. 24, no. iss. 1, pp. 65-75.
7. Malliarosa F. and Vazirgiannis M. Clustering and community detection in directed networks: A survey, Physics Reports, 2013, Vol. 533, pp. 95-142.
8. Landau L. and Lifshitz E. Theory of Elasticity (3rd ed.). Oxford: Butterworth Heinemann, 1986.
9. Tselykh A., Vasilev V. and Tselykh L. Fuzzy graphs clustering with quality relations functionals in cognitive models, in Advances in Intelligent Systems and Computing, 2016.
10. Fortunato S. Community detection in graphs, Physics Reports, 2010, Vol. 486, p. 75-174.
11. Nepusz T., Petroczi A., Negyessy L. and Bazsу F. Fuzzy communities and the concept of bridgeness in complex networks, Phys. Rev., 2008, Vol. 77, no. 1.
12. Fortunato S. and Hric D. Community detection in networks: A user guide, Physics Reports, 2016, Vol. 659, pp. 1-44.
13. Mu C., Liu Y., Liu Y., Wu J. and Jiao L. Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure, Physica A, Vol. 408, pp. 47-61.
14. Chen X. A new clustering algorithm based on near neighbor influence, Expert Systems with Applications, 2015, Vol. 42, pp. 7746-7758.
15. Šubelj L. and Bajec M. Group detection in complex networks: an algorithm and comparison of the state of the art, Physica A, 2014, Vol. 397, pp. 144-156.
16. Min D., Yu K. and Li H.-J. Refinement of the community detection performance by weighted relationship coupling., Pramana - Journal of Physics, 2017, Vol. 88, no. 3, pp. 44.
17. Xu Y., Xu H. and Zhang D. A novel disjoint community detection algorithm for social networks based on backbone degree and expansion, Expert Systems with Applications, 2015, Vol. 42, pp. 8349-8360.
18. Yang B., He H. and Hu X. Detecting community structure in networks via consensus dynamics and spatial transformation, Physica A, Vol. 483, pp. 156-170.
19. Bertsekas D.P. Constrained Optimization and Lagrange Multiplier Methods, Belmont, MA: Athena Scientifi, 1996.
20. Feynman R., Leighton R. and Sands M. The Feynman lectures on physics, Vol. 1, Reading, Mass: Addison-Wesley Publishing Company Inc., 1963.
21. Horn R. и Johnson C. Matrix analysis, Second Edition ред., New York: Cambridge University Press, 2013.
22. Zachary W. An Information Flow Model for Conflict and Fission in Small Groups, Journal of Anthropological Research, 1977, Vol. 33, no. 4, pp. 452-473.
23. Lusseau D., Schneider K., Boisseau O., Haase P., Slooten E. and Dawson S. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol. 54 (4) (2003) 396–405, Behav. Ecol. Sociobiol., 2003, Vol. 54 (4),
pp. 396-405.
24. Lusseau D. and Newman M.E.J. Identifying the role that animals play in their social networks, in Proceedings of the Royal Society of London. B, Biological Sciences, 2004.
25. Girvan M. and Newman M.E.J. Community structure in social and biological networks, in Proceedings of the National Academy of Sciences, 2002.
26. Ferreira F., Jalali M. and Ferreira J. Integrating qualitative comparative analysis (QCA) and fuzzy cognitive maps (FCM) to enhance the selection of independent variables, Journal of Business Research, 2016, Vol. 69, pp. 1471-1478.
27. Newman M. Fast algorithm for detecting community structure in networks, Physical Review E, 2004, Vol. 69, pp. 1-5.
28. Wu Q., Qi X., Fuller E. and Zhang C.-Q. Follow the Leader”: A Centrality Guided Clustering and Its Application to Social Network Analysis, Scientific World Journal, 2013, Vol. pp. 1-9.
29. Newman M.E.J. Detecting community structure in networks, The European Physical Journal B, 2004, Vol. 38, no. 2, pp. 321-330.
30. Zhao P. and Zhang C.-Q. A new clustering method and its application in social networks," Pattern Recognition Letters, 2011, Vol. 32, pp. 2109-2118.
31. Balakrishnan H. and Deo N. Detecting Communities using Bibliographic Metrics, in IEEE International Conference on Granular Computing, 2006.
32. Fortunato S., Latora V. and Marchiori M. A Method to Find Community Structures Based on Information Centrality, 2004.
33. Lusseau D. The emergent properties of a dolphin social network, in Proceedings of the Royal Society of London Series B-Biological Sciences, 2003.

Comments are closed.