Some Other Applications in Community Graph under the Preview of Social Graph Using Graph-Mining Techniques

Introduction

Day by day the applications on graphs are increasing rapidly leading to increase in size and complexities of graph. To represent a large community graph in the memory is a very challenging and rather difficult task. The direct visualization of such a large community graph is beyond human capability. The visualization can be achieved by compressing a large community graph into a smaller one which ultimately contains all the information’s related to the nodes of the community graph. Representation and compressing of such kind of community graph without knowledge loss presents a new challenge to graph mining. One issue in this direction is that, the huge community graph may severely restrict the application of existing pattern mining technologies. The compressed community graph should conserve the characteristics of the original community graph. So that visualization becomes easier and the process of knowledge extraction can be carried out more efficiently and easily. Graph compression problem can be addressed by clustering algorithms, as group members have similar characteristics and can be represented by super nodes. Similar work is done by graph partitioning algorithms by Fjallstrom (1998) and Elsner (1997), which can be used to detect hidden community structures. Most of these algorithms are based on the distance matrix, and do not focus on the structure of the original graph. Another feasible technique is to construct a small graph consisting of a set of the most important nodes and edges. Much literature has discussed how to rank the centrality of nodes and edges by Newman et al (2004) and Gert (1966). Another technique is the information-theoretic technique by Navlakha et al (2008) which can construct both lossless and lossy compressed graph representations. Such representation has two parts. The first one being the graph summary that captures the important communities and relationships in the original community graph and the second one is set of edge corrections which help to re-create the original community graph from a compressed community graph. The analysis of complex networks has become a hot research topic in the field of data mining. One of the examples is social network’s community network. Communities, also known as clusters, are often referred to as vertices with a high density of connections among them and seldom connected with the rest of the graph by Girvan et al (2002). Community detection provides valuable information about the structural properties of the network by Boccaletti et al (2006) and Girvan et al (2002), the interactions among the agents of a network by Blondel et al (2008) or the role the agents develop inside the network Wang et al (2010). Scalable Community Detection (SCD) by WWW (2014) detects disjoint communities in undirected and un-weighted networks by maximizing WCC, which is proposed community metric. Weighted Community Clustering (WCC) is a metric based on triangle structures in a community. A community (a module or a cluster) can be thought as a group of nodes with more interactions amongst its members than between its members and the remainder of the network by Girvan et al (2002). Such groups of nodes (communities) are interpreted as organizational units in social networks by Feld (1981) and Simmel (1964). The authors use graph theory’s some important techniques to solve the problem of partitioning a community graph to minimize the number of edges or links that connect different community by Rajaraman et al (2011). The aim of partitioning a community graph to sub-community graphs is to detect similar vertices which form a sub-community graph. For example, considering Facebook is a very large social graph. It can be partitioned into sub-graphs, and each sub-group should belong to a particular characteristics. Such cases the authors require graph partitions. In this partition, it is not mandatory that each sub-group contain similar number of members. A partition of a community graph is to divide into clusters, such that each similar vertex belongs to one cluster. Here a cluster means a particular community. A graph arises in many situations like web graph of documents, a social network graph of friends, a road-map graph of cities. Graph mining has grown rapidly for the last two decades due to the number and the size of graphs has been growing exponentially (with billions of nodes and edges), and from it the authors want to extract much more complicated information. Graph similarity has numerous applications in social networks, image processing, biological networks, chemical compounds, and computer vision, and therefore it has suggested many algorithms and similarity measures. Graph similarity is that “a node in one graph is similar to a node in another graph if their neighborhoods are similar” by Koutra et al (2011).