Authors A. N. Tselykh, V. S. Vasilev, L. A. Tselykh
Month, Year 03, 2018 @en
Index UDC 004.891.2
Abstract A new approach to clustering based on the model of division of vertices into groups based on higher potential energy of edges within groups than between the groups themselves is proposed. This method is implemented by minimizing the elastic strain potential energy functional for oriented weighted signed graphs. Existing structures in the adjacency matrix of a graph are expressed in its structure. The search for the best ordering of the graph vertices is carried out by means of the optimization process in the space of real numbers, which is inevitably displayed on the set of permutations of vertex indices. The method is developed for networks representing interrelations in economic systems. These relations are represented by heterogeneous factors and cause-effect relationships between them. Systems of objects and their relations are presented in the form of a fuzzy cognitive map, which, in fact, is a weighted oriented sign graph. Clustering methods are applied to this graph. The novelty of the approach is that the solution of the clustering problem is found as a solution to the optimization problem of the function of many variables (functionals). The proposed method uses a mechanical analogy, which is a special case of metric representations, which provides the convexity of the problem. This approach allows us to design various functionalities with a clear interpretation and predictability of the minimization process. The work of the algorithm is to find the numbering of the vertices of the graph, which reaches the lowest value of the functional. In this numbering, gradient components of the functional are used to determine the boundaries of the clusters. The criterion for classifying vertices as a single community is the proximity of the indices and the same gradient signs. These criteria are clearly formalized. The proposed algorithm classifies the vertices of a particular cluster and at the same time determines the order of the nodes in the cluster. This order reflects the degree of vertex distribution in relation to the intracluster energy to the energy of the extracluster bond. The hierarchical structure of the graph is revealed by recursive application of the proposed algorithm in each cluster without taking into account inter-cluster connections. The potential energy of the elastic deformation functional used in the clustering algorithm reflects the causal nature of the relationship of factors in the socio-economic system. Functional minimization is monotonous and requires no user intervention. The algorithm is computationally efficient.

Download PDF

Keywords Clustering; elastic deformation functional; oriented weighted graph; optimization methods; cognitive maps.
References 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.