Investigating Community Detection Algorithms in Real Networks using igraph

Brief description Enter a brief description of the project giving the student an idea of what the project is about Clustering is a fundamental problem in sciences: given a set (or system) of (any) discrete simple or structural data, extract from them some meaningful information that concerns their common properties and relations. In other words, from a given set of raw data, create a much smaller set of classes-groups where each data belongs to one of those groups, and data assigned in the same group, have some significant relation (e.g. commonalities, dependencies) to each other compared to the rest of the elements of the data set. The grouping can be defined according to one or more properties/features of the data (entities) of the set, which might concern pairwise relations between two entities of the set. In this case, one can associate the entities and their relation through a graph G(V;E). In such a modeling, the entities of the system specify the set of nodes V of the graph and relations between pairs of nodes of the system specify the edge set E of the graph. Relations between pairs of vertices of the graph may represent any kind of a relation, such as a positive, negative one, a dependency as well as a similarity of the values of the two vertices according to some function. For a system of entities, the clustering problem concerns the task of finding groups of vertices of the graph, called clusters or communities, such that the vertices within each group are highly connected to each other and while the inter-crossing connections between vertices of different groups are as few as possible. Communities indicate groups of vertices of the graph which are highly related to each other. The task of clustering has applications in many diverse fields such as social networks analysis, machine learning, pattern recognition, bioinformatics, Biology, Neuroscience and many more. There is an impressive literature developed around clustering algorithms most of which have been implemented in popular programming languages such as C, Python and Java, and many of those codes are publicly available. The project concerns an investigation of a package (collection of network analysis tools), called igraph, that provides both network visualization capabilities as well as implementations of many well-known clustering algorithms and network analysis tools. igraph can be programmed in Python, R and other programming languages. The project aims to explore the igraph package for computing clusters in real (public and private) data related to Astrophysics, Cosmology, Neuroscience and Social Sciences. We will consider igraph on Python or R. The student will have the opportunity to: (i) learn well Python or R (ii) learn the igraph package (iii) use it to compute and evaluate (existing) clustering algorithms on various interesting datasets available. Some of the algorithms to be investigated are provided by igraph; some other are provided from external sources. For the latter case, the student will investigate existing codes and will integrate them in igraph/Python. (iiii) Use igraph and Python/R to implement an algorithm for graph simplification showing the most important nodes of the graph based on a given clustering. (iiii) Use igraph and Python/R to implement an algorithm for graph simplification showing the most important nodes of the graph based on a given clustering.