Unapređena metoda promenljivih okolina za fazi klasterovanje na kompleksnim mrežama

Abstract

U okviru ovog rada predstavljena je nova VNS metoda za rešavanje problema fazi klasterovanja na kompleksnim mrežama. Za razliku od disjunktnog klasterovanja, gde jedan ˇcvor može samo u celini pripadati nekom klasteru, kod fazi klasterovanja ˇcvor može delimično pripadati različitim klasterima. Dakle, dimenzija rešenja problema fazi klasterovanja je nekoliko puta ve´ca nego u sluˇcaju disjunktnog klasterovanja, što dodatno usložnjava problem klasterovanja na kompleksnoj mreži. Kao lokalna pretraga, implementirana je efikasna metoda brze optimizacije fazi modularnosti, koja se u literaturi pokazala kao metoda sa najmanjim vremenom izvrašavanja do konvergencije. U fazi razmrdavanja, implementirane su i upoređene tri različite okoline, zasnovane na slučajnom izboru određenog broja čvorova čije se pripadnosti klasterima menjaju. Razvijena metoda testirana je na poznatim skupovima podataka Američki univerzitetski fudbal, Zaharijev karate klub i Mreži delfina. Eksperimentalni rezultati su pokazali da kombinacija sve tri okoline u fazi razmrdavanja daje najbolje rezultate na svim skupovima podataka.

In this paper, we present a new VNS method for fuzzy clustering on complex networks. Unlike disjoint clustering, where one node can only entirely belong to a cluster, in fuzzy clustering a node can partially belong to different clusters. Thus, the solution dimensionality of the fuzzy clustering algorithms is several times larger than in the case of disjoint clustering, which further complicates the clustering problem on complex networks. As a local search, an efficient method of fast fuzzy modularity optimization was implemented, which proved in the literature to be the method with the lowest execution time until convergence. In the shaking phase, three different environments were implemented and compared, based on a random selection of a number of nodes whose membership degrees change. The developed method was tested on the well-known data sets American University Football, Zachary Karate Club and Dolphin Network. Experimental results have shown that the combination of all three neighborhoods in the shaking phase gives the best results on all data sets.