Complex Query Processing on Web Graph: A Social Network Perspective
Mitra, Susanta, Bagchi, Aditya, Bandyopadhyay, A. K., Journal of Digital Information Management
ABSTRACT: A social network represents a social community as a directed graph. Communication on the Web has given rise to social network formation like, Web Community, Referral System etc. An earlier effort has proposed a data model for such Web-based social network. Present paper discusses the relevant index structures for processing queries on a social network schema based upon the proposed data model. The paper has also provided evaluation of the structural operators proposed in the data model and discussed their efficacy with query examples.
Categories and Subject Descriptors
E.1 [Data Structures]; Graphs and networks E.4 [Coding and Information Theory]; Data compaction and compression] H3.4 [Systems and software]; Information networks
Web graphs, Social networking, Data compression
Keywords: Web Graph, Social Network, Query Processing, XB-tree, Operator Evaluation
A social network is a social structure between actors (individuals, organization or other social entities) and indicates the ways in which they are connected through various social relationships like friendships, kinships, professional, academic etc. Some of the notable structural properties of a social network are connectedness between actors, reachability between a source and a target actor, reciprocity or pair-wise connection between actors with bi-directional links, centrality of actors or the important actors having high degree or more connections and finally the division of actors into sub-structures, like cliques or stronglyconnected components. The division of actors into strongly-connected components can be a very important factor for understanding a social structure, particularly the degree of cohesiveness in a community.
The formal representation of this pattern of relationships is a directed graph or digraph. In this graph, each member of a social community (people or other entities embedded in a social context) is considered as a node and communication (collaboration, interaction or influence) from one member of the community to another member is represented by a directed edge. In seventies Leinhardt first proposed the idea of representing a social community by a digraph . A graph representing a social network has certain basic structural properties, which distinguishes it from other type of networks or graphs. The number of nodes in a social network can be very small representing a circle of friends or very large representing a Web community.
The diverse and distributed nature of World-Wide-Web has given rise to variety of research into the Web's link structure ranging from graph-theoretic studies (connectivity, reachability etc.) to community mining (like, discovering strongly connected structural components etc.). Recently, Web has played a major role in the formation of communities (Cyber-communities or Web communities) where members or people from different parts of the globe can join the community for common interest. Thus Web has become a good source of social networks. Structural similarities of Web with a social network help in studying different sociological behaviors of a Web community through applications of graph theory and social network analysis. These similarities lead towards a progress in knowledge representation and management on the Web . Out of the many social network models on the Web, most commonly used one is called a referral network. In such a network, each node in the social network provides a set of links to its acquaintances that in turn become member nodes of the network. In the same way, these new nodes bring their acquaintances to the network again. This way the social network keeps on growing. So, the social network on the Web gives rise to an evolutionary graph. At any instant of time, when a query is raised on such an evolutionary graph, a snapshot of the concerned network, i.e. the node-edge structure at the instant of query, is considered for the purpose of query processing. …