Time-evolving web and social network graphs are modeled as a set of pages/individuals (nodes) and their arcs (links/relationships) that change over time. Due to their popularity, they have become increasingly massive in terms of their number of nodes, arcs, and lifetimes. However, these graphs are extremely sparse throughout their lifetimes. For example, it is estimated that Facebook has over a billion vertices, yet at any point in time, it has far less than 0.001% of all possible relationships. The space required to store these large sparse graphs may not fit in most main memories using underlying representations such as a series of adjacency matrices or adjacency lists. We propose building a compressed data structure that has a compressed binary tree corresponding to each row of each adjacency matrix of the time-evolving graph. We do not explicitly construct the adjacency matrix, and our algorithms take the time-evolving arc list representation as input for its construction. Our compressed structure allows for directed and undirected graphs, faster arc and neighborhood queries, as well as the ability for arcs and frames to be added and removed directly from the compressed structure (streaming operations). We use publicly available network data sets such as Flickr, Yahoo!, and Wikipedia in our experiments and show that our new technique performs as well or better than our benchmarks on all datasets in terms of compression size and other vital metrics.

Time-evolving graphs are structures that encapsulate how a graph changes over time. Thus, we not only have to deal with large graphs consisting of nodes and edges in the billions, but we must also keep track of when these edges activate and deactivate over long lifetimes. In this age of big historical data, we must make use of efficient time-evolving graph compressions, or we will find ourselves quickly out of main memory. These time-evolving graph compressions must not only be space efficient, but must also facilitate fast querying directly on the compressed graph. In this paper, define several novel time-evolving graph problems and develop algorithms to solve them directly on various, massive, synthetic and real-world time-evolving graphs compressed using our technique. Our experiments provide details of the compressed graph sizes, algorithm run times, and other metrics.

Time-evolving graphs represent a set of individuals (nodes) and their edges (relationships) over time. How these graphs are represented in data structures determines what information is easy to obtain from them. Now that we have such massive social networks with dynamic lifetimes, even basic data structures are too large to fit into main memory. Clearly, this poses a problem to areas such as time-evolving graph pattern analysis. Therefore, it is an interesting field of study to design time-evolving graph compressions that can efficiently answer certain queries about the graph at any given point in time.If a single snapshot of a graph at a moment in time can be considered a 2D matrix, then can we visualize these time-evolving graphs as 3D matrices and then use a novel technique to compress the entire graph over time. Our technique is based on our previous work using compressed binary trees. In this work, we adapt our strategy to compress time-evolving graphs, rather than static ones. We manage to maintain our minimal main memory overhead by not requiring an intermediate structure (e.g. adjacency list) to compress. This compression is queryable, meaning that the data can be read without decompression. It is also streaming, meaning that the data can be changed without decompression. This includes adding/removing edges in individual frames. We test our algorithms on public, anonymized, massive, time-evolving graphs such as Flickr, Yahoo!, and Wikipedia. Our empirical evaluation is based on several parameters including time to compress, size of compressed graph, and time to execute queries. Our compression rates are highly competitive, as we achieve the smallest representation of 4.9GB on our largest dataset which only spans three days yet occupies 21.5GB of space.

In this era of social networks, we find ourselves with a collection of massive, changing graphs. Each of these graphs contain a set of nodes (individuals) and a set of edges among the nodes (relationships). How a graph is represented in a data structure determines what information is easy to obtain from it. However, many graphs are so large that even basic data structure representations (e.g. adjacency lists) do not fit in main memory. Therefore, it is an interesting field of study to design compressed data structures that facilitate certain query functions. Since we are dealing with social networks, our structure will also be able to stream edges directly into the compressed graph. We introduce our social network compressed data structure as an indexed array of compressed binary trees. We further minimize memory overhead by directly constructing the graph without any intermediate structure. We also provide fast access methods for edge existence (does an edge exist between two nodes?), neighbor queries (list a node's neighbors), and streaming operations (add/remove nodes/edges). We test our algorithms on public, anonymized, massive graphs such as Friendster, Live-Journal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time to execute queries.

Social networks are constantly changing as new members join, existing members leave, and `followers' or `friends' are formed and disappear. The model that captures this constantly changing graph is the streaming graph model. Given a massive graph data stream wherein the number of nodes is in the order of millions and the number of edges is the tens of millions, we propose a simple algorithm to compress this graph without having read in the entire graph into the main memory. Our algorithm uses the quadtree data structure that is implicitly constructed to produce the compressed graph output. As a result of this implicit construction, our algorithm allows for node and edge additions/deletions that directly modifies the output compressed graph. We further develop algorithms to solve edge queries (is there any between two nodes?) and node queries (for a given node, list all its neighbors) that directly operates on the compressed graph. We have performed extensive empirical evaluations of our algorithms using publicly available, large social networks such as LiveJournal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time and memory size required to execute queries. We have also presented extensions to the compression algorithm that we have developed.

Studying the properties of Online Social Networks (OSNs) and other real world graphs have gained importance due to the large amount of information available from them. These large graphs contain data that can be analyzed and effectively used in advertising, security and improving the overall experience of the users of these networks. However, the analysis of these graphs for studying specific properties requires combinatorially explosive number of computations. Compute Unified Device Architecture (CUDA) is a programming model available from Nvidia for solving general-purpose problems using the massively parallel and highly multi-threaded Graphics Processing Units (GPUs). Therefore, using GPUs to solve these types of problems is appropriate. In addition, due to the properties of real-world data, the graphs being considered are sparse and have irregular data dependencies. Hence, using efficient techniques to store the graph data for initial preprocessing and final computation by taking advantage of heterogeneous CPU-GPU systems can address these issues. In this paper, we are interested in studying different properties of these real-world entities that transform into the following graph problems: a) identifying a missing edge, which when added would result in maximum increase in the number of triangles, b) identifying an existing edge whose removal would result in the maximum decrease in the number of triangles, c) identifying an existing edge whose removal would increase the number of connected components in the graph. In this paper, we develop and implement algorithms to solve the above problems using both CPU and GPU. Specifically, given a graph G = (V, E), we provide algorithms for the following: a) find (vi, Vj) ∉ E, such that Δf- Δcis maximized, where Δfand Δcare the number of triangles in Gm= (V, E ∪(vi, Vj)) and G, respectively, b) find a (vi, Vj) ϵ E, such that Δc- Δfis maximized, where Δfand Δcare the number of triangles in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively, c) find a (vi, Vj) ϵ E, such that Φc> Φc, where Φcand Φcare the number of connected components in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively. We implement the algorithms using a GPU and achieve a 10 × speedup as compared to a sequential implementation. Thereafter, we design a heuristic for finding an edge whose existence would result in the maximum increase in the number of triangles. The heuristic is implemented and the results are reported and compared to those of the regular algorithm on the GPU.

Virtual world and other collaborative applications are increasingly becoming popular among Internet users. In such applications, users interact with each other through digital entities or avatars. In order to preserve the user experience, it is important that certain Quality of Service (QoS) requirements (e.g., delay and bandwidth) are satisfied by the interactions. These QoS requirements are usually defined by the application designer. When applications with such QoS requirements are being deployed on a network of servers, an appropriate set of servers capable of satisfying the QoS constraints of the interactions must be identified. This identification process is nothing, but the subgraph homeomorphism problem. In this paper, we present polynomial-time solutions for a special case of this problem viz. subtree homeomorphism problem, wherein the guest and the host graphs are both trees. We also discuss generalizations of the subtree homeomorphism problem and present polynomial-time solutions.

Currently, workflow systems are either XML based or component based. Both paradigms have usability deficiencies. XML is not designed for procedural programming. Legacy code is difficult to adapt to component based systems. We propose a new paradigm by adding workflow keywords to an existing high-level language. This approach, called GroupSpeak, uses a procedural style of programming and allows for easy introduction of workflow patterns to legacy code. The programmer can leverage their existing knowledge of the high-level language to easily add workflow capabilities to their applications.

Collaborative multimedia applications (CMAs) on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include networked games and collaborative design and simulation. An important challenge in realizing CMAs is obtaining floor control, a problem in which the end-users compete among themselves to gain exclusive access to a shared resource. In this paper, we present deterministic and randomized distributed mechanisms for solving the floor control problem. In particular, we adapt the well-known MAC protocols viz. distributed queue dual bus (DQDB), ALOHA, and carrier sense multiple access (CSMA) as solutions for the floor control problem. Central to our adaptation is an algorithmic methodology that efficiently virtualizes the underlying network connecting the CMA participants so as to enhance the proposed solutions' performance. We present analytical and experimental studies on the performance of the proposed floor control protocols that bring out their essential characteristics.

Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, distributed database replication, and online games. This type of application requires a multicasting subnetwork, using which messages should arrive at the destinations within a specified delay bound. These applications also require that destinations receive the message from the source at approximately the same time. The problem of finding a multicasting subnetwork with delay and delay-variation bound has been proved to be an NP complete problem in the literature and heuristics have been proposed for this problem. In this paper, we provide an efficient heuristic to obtain a multicast subnetwork on an overlay network, given a source and a set of destinations that is within a specified maximum delay and a specified maximum variation in the delays from a source to the destinations. The time-complexity of our algorithm is O(|E|+nk log(|E|/n)+m2k), where n and |E| are the number of nodes and edges in the network, respectively, k is the number of shortest paths determined, and m is the number of destinations. We have shown that our algorithm is significantly better in terms of time-complexity than existing algorithms for the same problem. Our extensive empirical studies indicate that our heuristic uses significantly less runtime in comparison with the best-known heuristics while achieving the tightest delay variation for a given end-to-end delay bound

Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, collaborative design and simulation, distance learning, and online games. One of the important issues in collaborative applications is floor control wherein the end-users coordinate among themselves to gain exclusive access to the communication channel. An end-user who wins the floor, sends message to all other participating end-users. In this paper, to solve the floor control problem we present an implementation and evaluation of ALOHA and distributed queue dual bus (DQDB) distributed MAC (medium access control) protocols on overlay networks. As an initial step in the implementation of these MAC protocols, we propose an algorithm to construct an efficient communication channel among the Network Service Nodes (NSNs) in the overlay network. We also show that our implementation scheme (first one among decentralized floor control protocols) preserves the causal ordering of messages. We compare the efficiencies of the proposed implementation of floor control protocols using an analytical model that is verified using extensive simulation experiments.

A dynamic ad hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based on a hold-and-forward or shuttling method. We introduce the notion of connectivity-through-time and holding time to quantify the performance of the routing algorithms for various network connectivity scenarios. Using simulation, we study the throughput, reachability and message-reachability ratio of the proposed network under various connection/reconnection rates and holding times.

We present a distributed algorithm for rerouting to accommodate unlimited movement of mobile hosts in a mobile-mobile connection. The algorithm is source initiated-that is the source base station is responsible for the rerouting. The algorithm ensures that the establishment of non-optimal and incorrect paths is avoided and that no packets in the session are lost as there is always a path between the base stations in charge of the source and the destination. The design of this distributed algorithm ensures that the processing at the mobile hosts is kept to a minimum. In addition, the proposed framework for rerouting in mobile-mobile communications is independent of the type of rerouting scheme.

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structure can be constructed sequentially in O(n) time and O(n) space; using this data structure, each query on the length of the shortest path between any two intervals can be answered in O(1) time, and each query on the actual shortest path can be answered in O(k) time, where k is the number of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n/log n) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extended to solving the all-pair shortest path query problem on circular-arc graphs, both sequentially and in parallel, in the same complexity bounds. As an immediate consequence of our results, we improve by a factor of n the space complexity of the previously best-known sequential all-pair shortest path algorithm for unweighted interval graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 249–258, 1998

The set of binary trees with n internal vertices can be totally ordered using a number of different representations. There are Cn binary trees in any such order where Cn denotes the nth Catalan number. Given a total order on the set of binary trees with n internal vertices and an integer i, 1 ⩽ i ⩽ Cn, the unranking problem is to generate the binary tree whose ordinal number is i. Given a binary tree with T with ordinal number j < Cn and an integer i, 1 ⩽ i ⩽ Cn - j, a slight generalization of the unranking problem, called the relative unranking problem, is to find the binary tree with ordinal number i relative to T. The relative unranking problem is motivated by its application to computing a Steiner minimal tree in parallel. In this paper, a computationally efficient algorithm for solving the relative unranking problem is presented. The algorithm is based on a certain directed graph, called the feasible suffix graph, whose combinatorial properties are of independent interest. One of the salient features of the algorithm is that the unranking time can be traded for space. Computational experience with the algorithm is reported.