О методе построения алгоритмов для решения задачи корреляционной кластеризации

Обложка

Цитировать

Полный текст

Аннотация

Развивается техника построения алгоритмов, основанных на структуре сети (NS-алгоритмы), для решения задачи корреляционной кластеризации (CCP) для знаковых сетей. Моделью знаковой сети выступает неориентированный и невзвешенный простой знаковых графов. Эта задача рассматривается в оптимизационной форме с функционалом ошибки в виде линейной комбинации межкластерной и внутрикластерной ошибок. Известно, что в данной постановке задача является NP-трудной. Техника построения NS-алгоритмов основана на системном подходе, представленном в виде общей схемы. Схема состоит из шести взаимосвязанных блоков, каждый из которых отражает основные этапы решения CCP. Основная идея техники заключается в комбинировании модулей, представляющих каждый блок схемы. Предложенный подход реализован в виде программного комплекса. В работе представлен модельный NS-алгоритм, построенный с помощью предлагаемой техники. Проведены вычислительные эксперименты на синтетических данных по сравнению модельного алгоритма с уже известными.

Полный текст

1. Introduction A network is a collection of real objects of an arbitrary nature, in which some pairs of these objects are connected. The network nodes can be objects from social, biological or telecommunications systems [1-3]. Signed networks are defined as an extension of networks that includes additional information about positive and negative links. The following tasks are related to the analysis and modeling of signed networks: balance recognition; searching for a subnetwork with certain properties; clustering tasks; generating signed network with given properties; signed network mining [4-7]. © 2025 Ibragimova, E. I., Semenova, D. V., Soldatenko, A. A. image This work is licensed under a Creative Commons “Attribution-NonCommercial 4.0 International” license. image Ibragimova, E. I. et al. A technique of algorithms construction for solving a correlation clustering … 131 Integer programming image Polynomial integer programming Linear programming LP- KwikCluster Mixed integer programming Semi-defined programming Mathematical programming Relocation algorithms CCP solution approaches Rounding in general graphs Exact algorithms Heuristic algorithms Other algorithm adaptation Graph matrix Graph- theoretic formulation Iterated local search CarV eR Network structure Relocation heuristic KwikCluster Variable neigh- bourhood search Tabu search Figure 1. CCP solution approaches Our research focuses on the Correlation Clustering problem (CCP). A historical overview of the problem is given in [8], an overview of existing solution methods is given in [9]. There are two main approaches to solving the correlation clustering problem [9]. Figure 1 shows the approaches to solving the correlation clustering problem. The first approach is based on the representing of the correlation clustering problem as a mathematical programming problem (e.g., linear, integer, semi-definite, etc.). [9, 10]. The second approach is based on a graph-theoretic representation of the signed network. There are two types of algorithm: those based on the graph’s structure (NS-algorithms) [9, 11-13]; and those based on the graph’s matrix representation [9, 14]. The following results refer to the former, i. e. NS-algorithms. The definitions and the formulation of the problem of correlation clustering of signed networks necessary for further exposition are given in section 2. Section 3.1 describes the general scheme of algorithm construction and analysis, as well as possible variants of blocks. Section 3.2 describes the program complex for solving the CCP problem and investigates a new algorithm
×

Об авторах

Э. И. Ибрагимова

Сибирский федеральный университет

Email: EIbragimova@sfu-kras.ru
ORCID iD: 0000-0002-6852-2281
Scopus Author ID: 58766400800

Assistant of Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

Д. В. Семенова

Сибирский федеральный университет

Email: DVSemenova@sfu-kras.ru
ORCID iD: 0000-0002-8670-2921
Scopus Author ID: 49261191500
ResearcherId: O-3107-2019

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

А. А. Солдатенко

Сибирский федеральный университет

Автор, ответственный за переписку.
Email: ASoldatenko@sfu-kras.ru
ORCID iD: 0000-0001-6708-4753
Scopus Author ID: 57194285182
ResearcherId: O-8550-2019

Candidate in Physics and Mathematics, Associate Professor of the Department of Higher and Applied Mathematics

д. 79, пр. Свободный, г. Красноярск, 660041, Российская Федерация

Список литературы

  1. Maatouk, A., Hajri, S. E., Assaad, M. & Sari, H. On optimal scheduling for joint spatial division and multiplexing approach in fdd massive mimo. IEEE Trans Signal Process 67, 1006-10213 (2018).
  2. Arinik, N., Figueiredo, R. & andLabatut, V. Multiple partitioning of multiplex signed networks: Application to European parliament votes. Social Networks 60, 83-102 (2020).
  3. Abdelnasser, A., Hossain, E. & Kim, D. I. Clustering and resource allocation for dense femtocells in a two-tier cellular OFDMA network. IEEE Trans Wireless Communications 13, 1628-1641 (2014).
  4. Hüffner, F., Betzler, N. & Niedermeier, R. Optimal Edge Deletions for Signed Graph Balancing in Experimental Algorithms (ed Demetrescu, C.) (Springer Berlin Heidelberg, Berlin, Heidelberg, 2007), 297-310.
  5. Figueiredo, R. & Frota, Y. An improved Branch-and-cut code for the maximum balanced subgraph of a signed graph 2013. ArXiv: abs/1312.4345.
  6. Figueiredo, R. & Frota, Y. The maximum balanced subgraph of a signed graph: Applications and solution approaches. European Journal of Operational Research 236 (2014).
  7. Tang, J., Chang, Y., Aggarwal, C. C. & Liu, H. A Survey of Signed Network Mining in Social Media. ACM Computing Surveys CSUR 49, 1-37 (2015).
  8. Il’ev, V., Il’eva, S. & Kononov, A. Short Survey on Graph Correlation Clustering with Minimization Criteria in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2016), 25-36.
  9. Wahid, D. F. & Hassini, E. A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis. Oper. Res. Forum 47 (2022).
  10. Queiroga, E., Subramanian, A., Figueiredo, R. & Frota, Y. T. Integer programming formulations and efficient local search for relaxed correlation clustering. Journal of Global Optimization 81, 919-966 (2021).
  11. Ailon, N., Charikar, M. & Newman, A. Aggregating inconsistent information: ranking and clustering in Symposium on the Theory of Computing (2005).
  12. Brusco, M. J. & Doreian, P. Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search. Social Networks 56, 70-80 (2019).
  13. Levorato, M., Figueiredo, R., Frota, Y. & Drummond, L. Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO Journal on Computational Optimization 5, 467-498 (2017).
  14. Doreian, P. & Mrvar, A. Partitioning signed social networks. Soc. Networks 31, 1-11 (2009).
  15. Harary, F. Structural Balance: A Generalization of Heider’s Theory. Psychological Review 63, 227-293 (1956).
  16. Graham, R. L., Knuth, D. E. & Patashnik, O. Concrete Mathematics: A Foundation for Computer Science 2nd edn. 657 pp. (Addison-Wesley, Massachusetts, USA, 1994).
  17. Doreian, P. & Mrvar, A. A partitioning approach to structural balance. Social Networks 18, 149-168 (1996).
  18. Bansal, N., Blum, A. & Chawla, S. Correlation Clustering. Machine Learning 56, 89-113 (2002).
  19. Soldatenko, A. A., Semenova, D. V. & Ibragimova, E. I. An approach to analyzing and constructing algorithms for solving a one clustering problem on signed graphs. Applied discrete mathematics, 112-127 (2024).
  20. Ibragimova, E. I., D. V. Soldatenko, A. A. & Semenova. Comparison of Two Heuristic Algorithms for Correlation Clustering Problem Solving in 2023 5th International Conference on Problems of Cybernetics and Informatics (PCI) (IEEE, 2023), 1-4.
  21. Soldatenko, A., Semenova, D. & Ibragimova, E. On heuristic algorithm with greedy strategy for the Correlation Clustering problem solution in Lecture Notes in Computer Science (Germany, Heidelberg, Springer-Verlag, 2023), 462-477.
  22. Waxman, B. M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications 6, 1617-1622 (1988).
  23. Ciotti, V., Bianconi, G., Capocci, A., Colaiori, F. & Panzarasa, P. Degree correlations in signed social networks. Physica A: Statistical Mechanics and its Applications, 25-39 (2015).
  24. Aniyan, A. & Naduvath, S. Induced signed graphs of some classes of graphs. Proceedings of the Jangjeon Mathematical Society 23, 283-291 (2020).
  25. Sudheer, N., George, A. C., Aniyan, A. & Naduvath, S. Some new results on colour-induced signed graphs. Acta Univ. Sapientiae Informatica 14, 338-353 (2022).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Ибрагимова Э.И., Семенова Д.В., Солдатенко А.А., 2025

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.