Evolutionary Algorithms For Community Detection In RDF Graphs

Networks form foundations of complex systems,from the human brain to computer communications,transportation infrastructures to online social systems,biological systems to financial markets.In today's real world,most of the systems we encounter are complex systems.These systems provide non-trivial topological features,meaning their topological patterns of connection between elements are neither restricted to symmetrical arrangements nor predictable outcomes(purely random).The network science research community designates these systems as complex networks.Complex networks represent myriad real-world systems domains including man-made systems such as the Internet and Semantic Web applications.These Semantic Web knowledge domains describe the evolution of the World Wide Web(WWW)by making it programmable and Internet data machine-readable.Describing these complex network structures improves our understanding of the physical patterns,biological,economic,andevolving social behaviors that shape our world.The task of describing structures of complex networks is called community detection problem and one of the challenges complex networks poses is visualizing massive data in these complex systems.In this dissertation,discovering communities in complex networks is a fundamental problem.The main idea and focus of this research work is detecting communities in Semantic Web knowledge domains also known as Resource Description Framework(RDF)graphs that are directed,labeled,and sometimes are weighted graphs.Based on our research main idea of detecting communities in RDF graphs,our research work commenced by providing a precise description of what an RDF graph is and the main contribution of our research work is summarized as follows:(1)Our first main contribution,we have investigated the design and development of three new major algorithms for detecting communities in domain-specific knowledge bases-RDF graphs and these algorithms are:(a)Search,Traverse,and Ranking Algorithm-we have designed and developed this algorithm basing on the end-user or expert-free,the concept of private datasets(PDS),and the influence of the domain-expert at the entity level of an RDF graph that SHE identifies and assign weight to an instance or entity that influence the ranking of the obtained communities.Additionally,this algorithm considers four factors including first the subsumption weight being the weight that influences the path rank.The second factor is entity or node score-a measure of entity importance within an RDF graph.The entity score depends both,on the incoming links and the outgoing links,the third factor is link score that is an automatically assigned score value that first looks at the weight cores of entities the link is connecting,and the fourth factor is the domain-expert score these are weights assigned by the domain-expert to an RDF resource of interests from the expert-free in the domain-specific knowledge base.The obtained results of our algorithm are excellent;(b)A Spectral-Clustering Based Community Detection Algorithm-we have designed and developed this algorithm to detect communities by defining Diplacian using stationary probabilities of the Markov chain that govern random walks in digraphs.Simply our algorithm does not use node degrees to detect communities and the advantage is that it detects communities in RDF graphs by mintaining or without having to change the directionality of arcs or links.The obtained results are good and promising;(c)Modularity Based Community Detection Algorithm for RDF graphs-we have adapted the Louvain method for partitioning directed graphs into groups of related things and to be specific our algorithm uses two parameters;the randomized parameter for better decomposition of the graph and the resolution parameter to detect the number of communities in domain-specific knowledge bases.The obtained results are preliminary and are very good.(2)Our second main contribution,we looked at the concept of evolutionary algorithms and managed to propose a framework for detecting communities in RDF graphs based on genetic algorithms.