Search

Sustavi preporuke temeljeni na kolaborativnom filtriranju (engl. collaborative filtering recommender system) za identifikaciju sličnih proizvoda koriste algoritme za otkrivanje zajednica (engl. community detection algorithms) u grafovima. S tim ciljem je u ovom radu provedena analiza tih algoritama za pronalaženje zajednica bez preklapanja. Analizirani algoritmi su: Louvain, Leiden, širenje oznaka, infomap i Constant Potts Model. Algoritmi su provedeni nad stvarnim grafovima od kojih su neki pohranjeni u graf bazu podataka, a to su karate klub, firentinske obitelji, glavni gradovi svijeta i Amazon proizvodi te nad sintetičkim LFR grafovima. Dobivene zajednice uspoređene su po unutrašnjim metrikama modularnosti i provodnosti te vanjskim metrikama normalizirane F1 vrijednosti i normaliziranom uzajamnom sadržaju informacija. Collaborative filtering recommender systems use algorithms for community detection in graphs to identify similar products. This study analyzes community detection algorithms for crisp communities for this purpose. The analyzed algorithms include Louvain, Leiden, label propagation, infomap, and Constant Potts Model. These algorithms were applied to real-world graphs, some of which were stored in a graph database, including the karate club, Florentine families, world capitals, Amazon products, as well as synthetic LFR graphs. The obtained communities were compared using internal metrics such as modularity and conductance, as well as external metrics such as normalized F1 score and normalized mutual information.

Analiza društvene mreže postupak je koji nam daje bolje razumijevanje određene mrežne strukture te je široko primjenjiv u različitim područjima kao što su marketing, biologija, informacijska sigurnost... Prilikom analize društvene mreže često se javlja problem identifikacije najvažnijih vrhova. U tu svrhu promatrali smo algoritme kao što su centralnost stupnja vrha, centralnost bliskosti, centralnost središnjeg položaja, centralnost svojstvenog vektora te PageRank centralnost. Za svaku centralnost dali smo mane i prednosti te smo došli do zaključka da nam centralnost svojstvenog vektora te PageRank centralnost daju najbolju informaciju o važnosti pojedinog vrha u mreži. U društvenoj mreži vrlo je bitno podijeliti korisnike u neke manje zajednice kako bi obuhvatili ljude sa istim interesima i ponašanjima. Prošli smo kroz algoritme detekcije klika, Louvainov algoritam te Girvan-Newman alogoritam. Nakon što smo usporedili algoritme te istaknuli njihove prednosti i mane mogli smo doći do zaključka da će nam najčešće Louvainov algoritam dati najbolju podjelu mreže na zajednice. Social network analysis is a procedure that gives us a better understanding of a certain network structure and is widely applicable in various fields such as marketing, biology, information security... When analyzing a social network, the problem of identifying the most important nodes often arises. For this purpose, we observed algorithms such as vertex degree centrality, closeness centrality, betweenness centrality, eigenvector centrality and PageRank centrality. For each centrality, we gave disadvantages and advantages, and we came to the conclusion that the centrality of the eigenvector and the PageRank centrality give us the best information about the importance of an individual vertex in the network. In a social network, it is very important to divide users into smaller communities in order to include people with the same interests and behaviors. We went through clique detection algorithm, the Louvain algorithm and the Girvan-Newman algorithm. After comparing the algorithms and highlighting their advantages and disadvantages, we could come to the conclusion that the Louvain algorithm will most often give us the best division of the network into communities.

Teorija grafova je grana matematike s brojnim primjenama u teoriji kompleksnih mreža, području kojem pripada i problem prepoznavanja zajednice. Problem prepoznavanja zajednice odnosi se na pronalaženje prirodne podjele mreže na grupe čvorova takve da postoji mnogo veza unutar zajednice, a nekoliko (manje) veza među grupama. U ovoj temi obradit će se problem prepoznavanja zajednica u usmjerenim acikličkim grafovima i, konkretnije, kurikulnim grafovima. Kurikulni grafovi su grafovi koji predstavljaju nastavne jedinice i njihovu međusobnu povezanost. Predstavit će se osnovni pojmovi teorije grafova te relevantni matematički rezultati. Opisat će se primjeren matematički model za problem prepoznavanja zajednica. Obradit će se tri modifikacije algoritma za propagaciju oznaka koje rješavaju problem prepoznavanja zajednica u usmjerenom acikličkom grafu. Algoritmi će se implementirati, testirati i usporediti. Izradit će se računalna aplikacija s grafičkim sučeljem prikladnim za crtanje grafova, i provođenje eksperimenata sa implementiranim algoritmima. Implementirani algoritmi primijenit će se za rješavanje problema grupiranja pojmova u nastavne cjeline. Graph theory is a branch of mathematics with numerous applications in the theory of complex networks, which includes the problem of community detection. The problem of community detection involves finding a natural division of a network into groups of nodes such that there are many connections within the group and few (or less) connections between groups. In this thesis, we will address the problem of community detection in a directed acyclic graph and, more concrete, curriculum graphs. Curriculum graphs are graphs that represent teaching units and dependencies between them. This paper will cover the basic concepts of graph theory and relevant mathematical results. We will describe a suitable mathematical model for the problem of community detection. We will present three modifications of label propagation algorithms that solve the problem of community detection in directed acyclic graphs. The algorithms will be implemented, tested, and compared. An web-application with a graphical interface suitable for graph drawing and doing the experiments with implemented algorithms. The implemented algorithms will be applied to solve the problem of grouping concepts into teaching units.

U radu je opisano pet algoritama za otkrivanje zajednica u društvenim mrežama. Pored najpoznatijeg Girvan-Newmanovog algoritma opisani su Louvain, Surprise, Leiden i Walktrap algoritmi. Kao dio rada implementirana je programska podrška koja pruža mogućnosti usporedbe algoritama i generiranja umjetnih mreža. Rezultati algoritama vrednovani su pomoću deset evaluacijskih mjera na umjetno generiranim mrežama, dobivenim pomoću Watts-Strogatz modela te na primjerima mreža iz stvarnog svijeta iz biblioteke SNAP. Thesis describes five community detection algorithms for finding communities in social networks. In addition to the most famous Girvan-Newman algorithm, there are described Louvain, Walktrap, Leiden and Walktrap algorithms. As part of the thesis there is implemented software which provides ability to compare algorithms and generate artificial networks. The results of algorithms are evaluated with ten evaluation measures on artificial networks that are created using Watts-Strogatz model and on the real world network examples from the SNAP library.

Poznati izazov u sustavima preporuke jest tzv. problem hladnog starta koji nastaje u ranoj fazi postprodukcije kada još nemamo zabilježene korisničke preference u obliku recenzija na temelju kojih bi sustav mogao generirati preporuke. U okviru rada, predloženo je rješenje koje koristi metodu samonadziranog učenja kojim se neuronska mreža uči reprezentacijama korisnika i sadržaja na temelju kojih se uz međusobnu usporedbu dolazi do najpoželjnije preporuke. Kako bi se dokazala uspješnost ove metode, dizajniran je sustav preporuke znanstvenih članaka. Rezultati ovog pristupa su zadovoljavajući. Kako bi se u budućnosti postigli još bolji rezultati, naučeni model trebao bi se iskoristiti u sklopu prijenosnog učenja (eng. transfer learning) uz prave korisničke recenzije. A well-known challenge in recommender systems is the so-called cold start problem that arises in the early stages of post-production when we do not yet have recorded user preferences in the form of reviews, based on which the system could generate recommendations. This final paper suggest a solution based on self-supervised learning in which the neural network learns the representations of users and the content on the basis of which they are compared to the most desirable recommendations. As part of proving proposed method, a system of recommending scientific articles has been developed. The results of this approach are satisfactory; however, in order to achieve even better results, the developed trained model should be used in transfer learning with real user reviews.

Analiza društvenih mreža postala je vrlo dinamično i unosno područje pojavom online društvenih mreža i povećanjem kapaciteta za njihovu obradu. Otkrivanje zajednica jedno je od najvažnijih područja unutar analize društvenih mreža. U ovom radu, predstavljen je pojam društvene mreže, njene karakteristike, pojam zajednice u kontekstu društvenih mreža i problematika procjene njihove kvalitete. Nadalje, napravljena je usporedba Girvan-Newman, Label Propagation i Clauset-Newman-Moore algoritama za otkrivanje zajednica. Analiza je provedena u dva dijela: prvo na umjetno generiranim mrežama proizvedenih Lancichinetti-Fortunato-Radicchi metodom, a potom na stvarnim podacima s društvene mreže Twitter. The arrival of online social networks and the increase in the capacity to process them has caused social network analysis to become a very dynamic and lucrative field. Community detection is one of the most important areas of social network analysis. This thesis presents the notion of a social network, its characteristics, the notion of community in the context of social networks and the problem of assessing their quality. Furthermore, a comparison of Girvan-Newman, Label Propagation and Clauset-Newman-Moore community detection algorithms was made. The analysis was performed in two parts: first on artificially generated networks produced by the Lancichinetti-Fortunato-Radicchi benchmark, and then on real data from the social media network Twitter.

U ovom završnom radu obrađen je jedan od najvažnijih problema u analizi društvenih mreža, a to je otkrivanje zajednica. Opisana je struktura društvenih mreža i mjere pomoću kojih se one analiziraju. Objašnjeni su postupci grupiranja u teoriji grafova. Proučeni su i opisani Girvan-Newman i Clauset-Newman algoritmi za otkrivanje nepreklapajućih zajednica u društvenim mrežama. Navedeni algoritmi provedeni su nad stvarnim skupom podataka te nad umjetno stvorenim skupom primjenom Watts-Strogatz modela te je dana usporedba njihovih rezultata. Opisan je pojam small-world fenomena te razvoj i svojstva Watts-Strogatz modela. This paper discusses one of the most important issuses in social network analysis which is community detection. A detailed description of a social network structure is given and measures used to analyze them. Different clustering techniques used in graph theory are also described. Steps of Girvan-Newman and ClausetNewman Moore algorithms for community detection are shown. The two algorithms are implemented in Snap.py library and evaluated on five real-world datasets as well as on generated random small-world graphs. Small-world phenomenon is described along with the evolution and characteristics of the Watts-Strogatz model.

Jedan od najvažnijih zadataka u analizi društvenih mreža jest otkrivanje zajednica s kohezivnim grupama aktora koji su sličniji jedni drugima nego ostalim aktorima u mreži. Algoritmi otkrivanja zajednica su vrlo često korišteni u analizi svojstava društvenih mreža. U ovome radu, osam algoritama otkrivanja zajednica koji su implementirani u knjižnici igraph su vrednovani i testirani na šest skupova podataka koji predstavljaju mreže iz stvarnog svijeta. Algoritmi su uspoređeni koristeći metrike kvalitete (npr. modularnost, provodnost) i također metrike sličnosti (npr. normalizirana zajednička informacija) ako je poznata prava struktura zajednica. Nadalje, pokazana je implementacija nekoliko metrika kvaliteta i sličnosti za igraph paket za programski jezik Python. Analiza pokazuje da Multilevel algoritam daje najbolje rezultate sveukupno, a Leading eigenvector algoritam najgore. One of the most important tasks of social network analysis is to detect communities with cohesive group of actors who are more similar to each other than to the other actors in the network. Community detection algorithms are widely used to analyze the properties of social networks. In this thesis, eight community detection algorithms which are implemented in igraph library are evaluated and tested on six datasets representing real-world networks. The algorithms are compared based on quality metrics (e.g. modularity, conductance), and also similarity metrics (e.g. normalized mutual information) if the ground-truth communities are known. Furthermore, implementation of several quality and similarity metrics for igraph package for Python is shown. The study reveals that the Multilevel algorithm obtains the best results overall, while Leading eigenvector algorithm obtains the worst one.

Proučavanje istraživačkog pitanja "otkrivanje zajednica u društvenim mrežama zasnovano na određivanju povjerenja između korisnika" provedeno je nad skupom podataka kreiranim temeljem analize više od 250 tisuća korisnika društvene mreže Facebook. Za potrebe rješavanja istraživačkog pitanja predložena je metoda SmartSocial Trust, a uz postojeće mjere evaluacije razvijena je nova mjera koeficijent SmartSocial Trust. Dobiveni rezultati uspoređeni su s teoretskim matematičkim modelom metode za klasifikaciju korisnika društvene mreže u društvene zajednice i referentnom state-of-the-art metodom iTrust. Prema svim parametrima evaluacije metoda SmartSocial Trust pokazala se kao najbolja. Ostvaren je sljedeći izvorni znanstveni doprinos: (i) model zajednica u društvenim mrežama zasnovan na povjerenju među korisnicima izvedenom iz atributa korisničkih profila i strukturnih svojstava društvenog grafa; (ii) metoda otkrivanja zajednica u društvenim mrežama koja obuhvaća postupke transformacije internetske društvene mreže u društveni graf i algoritam za izračun povjerenja u dobivenom društvenom grafu; (iii) laboratorijski prototip za otkrivanje zajednica u društvenim mrežama verificiran na referentnom skupu podataka „SmartSocial Trust“ stvorenom provođenjem društvenog eksperimenta u internetskom okružju. The research question "community detection in social networks based on a calculation of trust between users" was studied on the dataset created through the analysis of more than 250 thousand of Facebook users. The SmartSocial Trust method was proposed for solving the described research question. Further, in addition to the existing evaluation methods, a new measure, called the SmartSocial Trust coefficient, was developed. The achieved results were compared with a mathematical model for classification of social network users in communities based on the random classification and state-of-the-art reference iTrust method. Among the analysed methods, the SmartSocial Trust method proved to be the best according to all evaluation parameters. The original scientific contribution has been achieved as follows: (i) social community model based on a calculation of trust between online social network users, where trust is derived from user profile attributes and structural features of the social graph; (ii) social community detection method, which includes online social network transformation into social graph and the algorithm for calculating social trust based on the social graph; (iii) laboratory prototype for community detection in online social networks verified on the reference dataset “SmartSocial Trust” created by conducting a social experiment in the Internet environment.

U ovom radu je definiran pojam društvenih mreža te je opisana metoda otkrivanja zajednica u društvenim mrežama primjenom tri različita algoritma – Walktrap, Label-propagation i Girvan-Newman. Sva tri algoritma su opisana na konceptualnoj razini te vrednovana kroz dva odvojena testa. Kao metrike vrednovanja koriste se vrijeme izvođenja te modularnost. Prvi test koristi stvarne nepredvidive podatke prikupljene na društvenoj mreži Facebook . Drugi test koristi umjetno generiranu mrežu Small-world čiji parametri se mogu proizvoljno mijenjati. Vrednovanja se vrše koristeći programski jezik Python i pripadajuću knjižnicu igraph. Naposljetku, dobiveni rezultati su međusobno uspoređeni. This paper defines social network term and describes community detection methods in social networks using three different algorithms – Walktrap, Labe-propagation and Girvan- Newman. All three algorithms are conceptually described and evaluated through two separated tests. As evaluation metrics, run time and modularity are being used. The first test uses real and unpredictable data collected on social media network Facebook. The second test uses artificial network called Small-world network whose parameters can be changed. Evaluations are being made using Python programming language and related library igraph. Finally, given results are mutually compared.

Objašnjeno je što je društvena mreža i što predstavljaju vrhovi i bridovi društvene mreže. Objašnjene su važnosti otkrivanja analize društvenih mreža i otkrivanja zajednica. Opisana su dva algoritma za otkrivanje zajednica, Girvan-Neman i CNM algoritam. Opisani su koraci navedenih algoritama, primjeri njihovih rezultata te je dana usporedba modularnosti, provodljivosti i unutarnjoj gustoći. Opisane su i small-world mreže, njihova svojstva te Watts-Strogatz model za njihovo stvaranje. In this paper I explain social networks and what their nodes and vertices represent. I write about the importance of social network analysis and detecting communities. Two alghoritms are presented for detecting communities, Girvan-Newman alghoritm and CNM alghoritm. Their steps are explaind and they are compared by modularity, internal densitiy and conductance. I also describe small-world networks, their properties and Watts-Strogatz model.

Društveno umrežavanje, zahvaljujući različitim web-zasnovanim društvenim platformama, postaje sve popularnije. Društveni krugovi pomažu korisnicima organizirati i detektirati društvene skupine prijatelja u njihovoj osobnoj društvenoj mreži. Radi lakše vizualizacije dobivenih podataka te promatranja veza, koristi se neusmjereni težinski društveni graf. U radu su obrađene metode otkrivanja društvenih krugova, kao i njihova validacija na skupu stvarnih podataka. Praktični dio diplomskog rada sastoji se implementacije četiri algoritma za otkrivanje zajednica u mrežama i njihove validacije pomoću dvije mjere. Social networking is becoming increasingly popular thanks to various web - based social platforms. Social circles help users to organize and detect social groups of friends in their personal social network. In order to facilitate obtained data and observe connections, undirected weighted social graph is being used. This paper deals with different methods of discovering social circles, as well as their validation on a set of real data. The practical part of thesis consists of implementing four algorithm for detecting community networks and of their validation by using two measures.

U radu je opisana preliminarna analiza mreža koautorstva Sveučilišta u Rijeci za četiri odabrane sastavnice. Mreža koautorstva prikazuje suradnju znanstvenika u objavljivanju znanstvenih publikacija. Konstruira se tako da je svaki znanstvenik čvor, a veza između dvaju čvorova postoji ako su ta dva znanstvenika objavila zajedničku publikaciju. Težina veze predstavlja broj objavljenih publikacija dvaju znanstvenika. Cilj je analizirati i usporediti suradnju na nekoliko različitih sastavnica Sveučilišta u Rijeci. Za potrebe analize korištene su metode analize kompleksnih mreža. U prvoj fazi eksperimenta podaci su prikupljeni s mrežnih stranica Hrvatske znanstvene bibliografije (CROSBI) i obrađeni te formatirani u odgovarajući oblik. U drugoj fazi eksperimenta konstruirane su mreže koautorstva i provedena je analiza podataka. Prvo su analizirane i uspoređene numeričke vrijednosti globalnih mjera mreža. Nakon toga je prikazana analiza i vizualizacija zajednica na središnjoj razini mreže. Na kraju su na lokalnoj razini analizirani centralni čvorovi u mrežama primjenom triju različitih lokalnih mjera centralnosti. Pokazalo se da promatrane mreže imaju neka zajednička globalna svojstva, no rezultati ukazuju i na to da se sastavnice prilično razlikuju u broju i strukturi zajednica. Analizom na lokalnoj razini također je ustanovljeno da broj ostvarenih zajedničkih publikacija značajno varira po sastavnicama., In this paper we describe preliminary co-authorship network analysis performed for the four constituents of the University of Rijeka. Co-authorship network describes scientific collaboration among scientists. It is constructed in a way that each scientist is represented as a node and a link between two nodes is constructed if these two scientists collaborate on the same scientific publication. The weight on the link represents the number of scientific publications. The goal of this experiment has been to analyse and compare scientific collaboration among several constituents of the University of Rijeka. For this experiment the methods of complex networks analysis have been used. In the first phase of the experiment the dataset from web pages: Croatian Scientific Bibliography (CROSBI) is collected. In the second phase of the experiment five networks are constructed and analysed. The numeric values of the global network measures are analysed first. After that, the communities at the mesoscale network level are identified and visualised. At the end, central nodes are found (according to the three centrality measures). It is shown that all networks have similar global properties. However, there are differences between networks in the community structure. According to the local-level analysis, the number of publications among constituents vary substantially.