Community Detection and Ranking in Big Data Graphs

Community structures and relation patterns, and ranking them for social networks provide us with great knowledge about the network. A community is defined by determining a lower density of relations between groups comparing to higher density among every group. Such knowledge can be utilized for grouping similar, yet distinct, nodes with applications in health, marketing, and many more. The ever-growing variety of social networks necessitates detection of minute and scattered communities, which are important problems across different research fields including biology, social studies, physics, etc. As a result, analyzing complex networks has become very popular among researchers in academia and the industry. Interactions and inter-individual relations are captured and depicted as social networks graphs. The aforementioned structure analysis helps researchers determine the model, the type, and the degree of relationships. Besides, it can provide guides to predict the future behavior of social networks. There exist two different types of mining and analyses over social networks. The first is to analyze the structure, i.e. finding the k-influential nodes and network regions with the most evolved structure. The second is content-based analysis which is based on the information produced and transferred by the nodes of social networks. The second type of analyses is not suitable to detect and predict patterns or modeling of groups but it deals with optimizing the quality of the previously identified communities. Various methods have been developed to detect communities. Most of them are very expensive in both space and time. Community detection has different criteria and the most important community detection definitions criteria are as follows: a) Because of similarity between taste and desire among community members, communities are able to offer and exchange information; b) Detecting communities helps to understand the structure of the whole networks as the communities are partitions of the network organized by interest and individual functions; c) Detecting communities plays an important role in finding the overall information flow structure of networks, especially in large-scale networks like human brain network. Most network datasets lack a ground truth for communities. Therefore, communities are evaluated based on several features. In other words, the structure and quality of communities are estimated based on the given features. Modularity is one of the most popular criteria to evaluate the quality and structure of a given community detection algorithm. There is another method called Normalized Mutual Information (NMI). NMI measures detected communities accuracy by calculating the entropy of the founded community and the given ground truth. NMI, then, compares the detected communities with the initial structure and computes the accuracy percentage. Ranking communities is a novel research work. Node ranking based on their influence on the network exists in the literature. We extend the concept of ranking nodes and propose to rank the communities. The applications of such influence-based ranking include intrusion detection, target marketing, as well as recommendation systems