We present a two step procedure to identify long lasting communities, or evolutions, in social networks. First, we use axiomatic foundations to `rigorously' establish shorter, strongly-connected evolutions. In the second step, we use heuristics to combine these shorter evolutions to form longer evolutions. We apply the procedure on data generated from two networks - the DBLP co-authorship database and Live Journal blog data. We visually validate our algorithms by examining the topic evolution of the associated documents. Our results demonstrate that our algorithms, based solely on structural properties of the data (who interacts with whom), are able to track thematic trends in the literature. We then use a machine learning framework to identify the structural features of the early stages of a community's evolution are most useful for predicting the lifetime of the community. We find that (in order) size, intensity and stability are the most important features.

We present novel indexing and searching schemes for semantic graphs based on the notion of the i.degrees of a node. The i.degrees allow searches performed on the graph to use “type” and connection information, rather than textual labels, to identify nodes. We aim to identify a network graph (fragment) within a large semantic graph (database). A fragment may represent incomplete information that a researcher has collected on a sub-network of interest. While textual labels might be available, they are highly unreliable, and cannot be used for identification of hidden networks. Since this problem comes from the classically NP-hard problem of identifying isomorphic subgraphs, our algorithms are heuristic.

Trust is an important yet complex and little understood aspect of the dyadic relationship between two entities. Trust plays an important role in the formation of coalitions in social networks and in determining how high value of information flows through the network. We present algorithmically quantifiable measures of trust based on communication behavior. We propose that trust results in likely communication behaviors which are statistically different from random communications; detecting these trust-like behaviors allows us to develop a quantitative measure of who trusts whom in the network. We develop algorithms to efficiently compute such behavioral trust and validate these measures on the Twitter network.

We study information diffusion in real-life and synthetic dynamic networks, using well known threshold and cascade models of diffusion. Our test-bed is the communication network of the LiveJournal Blogosphere. We observe that the dynamic and static versions of the Blogograph, yield very different behaviors of the diffusion. It was earlier discovered that the communication dynamics of the Blogograph is quite high - over 60% of the links each week were not present in the previous week, though the size of the node set is relatively stable. Our models of the Blogograph evolution reproduce general stable statistics of the real-life Blogograph. We discover that the diffusion footprint on our models closely approximate the diffusion footprint of the real-life dynamic network.

This work experimentally examines different notions of stability of the behavior of individuals and groups in a network of blogs. Our experiments are conducted on data collected from LiveJournal. All stability notions aim to locate stable behavior within an individual's area, which is defined in a variety of manners. Our experiments confirm an earlier observation of the highly dynamic nature of the network. Roughly 70% of the communication of a typical week was not observed in the previous week. Depending on the definition of stability and area used, we find small, but highly stable, sets of individuals with stable behavior in the network.

In this work, we present the software library graphOnt. The purpose of this library is to automate the process of dynamically extracting ldquointerestingrdquo graphs from semantic networks. Instructions on the extraction are fed into the library via an ontological language specification custom built for this application. A set of SPARQL queries are used to define vertices and edges in the constructed graph. Extracted graphs are returned using the JUNG framework, which offers many algorithmic and visualization options. This work allows a set of individuals analyzing the same semantic network to extract and analyze dynamically created graphs using sophisticated, specific algorithmic tools without needing to manually construct classical graphs from the data.

In this paper, we present a novel model for the evolution dynamics of social networks which supports public communication (communication which is visible to all members of the network). Though our model is general, it is particularly applicable to blog-networks, which is the domain we use for testing. We use a directed graph, the blogograph, to represent the communication activity in the Blogosphere. Our model is based on three fundamental principles for describing evolution dynamics in social networks.

We present a machine learning approach to discover the agent dynamics that drives the evolution of the social groups in a community. We set up the problem by introducing an agent-based hidden Markov model for the agent dynamics: an agent's actions are determined by micro-laws. Nonetheless, We learn the agent dynamics from the observed communications without knowing state transitions. Our approach is to identify the appropriate micro-laws corresponding to an identification of the appropriate parameters in the model. The model identification problem is then formulated as a mixed optimization problem. To solve the problem, we develop a multistage learning process for determining the group structure, the group evolution, and the micro-laws of a community based on the observed set of communications among actors, without knowing the semantic contents. Finally, to test the quality of our approximations and the feasibility of the approach, we present the results of extensive experiments on synthetic data as well as the results on real communities, such as Enron email and Movie newsgroups. Insight into agent dynamics helps us understand the driving forces behind social evolution.

We present a modeling laboratory, Virtual Laboratory for the Simulation and Analysis of Social Group Evolution (ViSAGE), that views the organization of human communities and the experience of individuals in a community as contingent upon on the dynamic properties, or micro-laws , of social groups. The laboratory facilitates the theorization and validation of these properties through an iterative research processes that involves (1) forward simulation experiments, which are used to formalize dynamic group properties, (2) reverse engineering from real data on how the parameters are distributed among individual actors in the community, and (3) grounded research, such as participant observation, that follows specific activities of real actors in a community and determines if, or how well, the micro-laws describe the way choices are made in real world, local settings. In this article we report on the design of ViSAGE. We first give some background to the model. Next we detail each component. We then describe a set of simulation experiments that we used to further design and clarify ViSAGE as a tool for studying emergent properties/phenomena in social networks.

The power of social values that helps to surreptitiously shape or formulate our behavior patterns is not only inevitable, but also influential as the directions of our decision making can never seem to escape the impact of this hidden agent. Therefore, the search of such power agent can be validated through a machine learning approach that enables us to discover the agent dynamics in which drives the evolution of the social groups in a community. By doing so, we set up the problem by introducing a parameterized probabilistic model for the agent dynamics: the acts of an agent are determined by micro-laws with unknown parameters. Our approach is to identify the appropriate parameters in the model. To solve the problem, we develop heuristic expectation-maximization style algorithms for determining the micro-laws of a community based on either observed communication links between actors, or the observed evolution of social groups. We present the learning results from the synthetic data as well as the findings on real communities, e.g., Enron email and movie newsgroups.

We present an extended version of a software system SIGHTS (statistical identification of groups hidden in time and space), which can be used for the discovery, analysis, and knowledge visualization of social coalitions in communication networks such as Blog-networks. The evolution of social groups reflects information flow and social dynamics in social networks. Our system discovers such groups by analyzing communication patterns. The goal of SIGHTS is to be an assistant to an analyst in identifying relevant information. The functionality of SIGHTS includes: discovery of coalitions (clusters) and their leaders; finding hidden groups using communication persistence techniques; discovering hidden groups in communication streams; matching topics of the blogs and detecting sentiments; tracking the evolution of clusters; visualization of collections of individual clusters.

This paper describes a computational approach to designing a digital microfluidic system (DMFS) that can be rapidly reconfigured for new biochemical analyses. Such a “lab-on-a-chip” system for biochemical analysis, based on electrowetting or dielectrophoresis, must coordinate the motions of discrete droplets or biological cells using a planar array of electrodes. The authors have earlier introduced a layout-based system and demonstrated its flexibility through simulation, including the system's ability to perform multiple assays simultaneously. Since array-layout design and droplet-routing strategies are closely related in such a DMFS, their goal is to provide designers with algorithms that enable rapid simulation and control of these DMFS devices. In this paper, the effects of variations in the basic array-layout design, droplet-routing control algorithms, and droplet spacing on system performance are characterized. DMFS arrays with hardware limited row-column addressing are considered, and a polynomial-time algorithm for coordinating droplet movement under such hardware limitations is developed. To demonstrate the capabilities of our system, we describe example scenarios, including dilution control and minimalist layouts, in which our system can be successfully applied.

This paper describes the LINK software system, which provides not only a graph editor and graph library, but a computing environment that employs object-oriented Scheme to provide a flexible workbench for algorithm learners and experimenters. Copyright © 2000 John Wiley & Sons, Ltd.

Every graph with n vertices and m edges has an independent set containing at least $n^2 / (2m + n)$ vertices. This paper presents a parallel algorithm that finds an independent set of this size and runs in $O( \log^3 n )$ time on a CROW PRAM with $O( ( m + n)\alpha ( m,n )/ \log^2 n)$ processors, where $\alpha ( n,m )$ is a functional inverse of Ackerman’s function. The ideas used in the design of this algorithm are also used to design an algorithm that, with the same resources, finds a vertex coloring satisfying certain minimality conditions.

A new parallel algorithm for the maximal independent set problem is constructed. It runs in $O(\log ^4 n)$ time when implemented on a linear number of EREW-processors. This is the first deterministic algorithm for the maximal independent set problem (MIS) whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor.

The problem of constructing in parallel a maximal independent set of a given graph is considered. A new deterministic NC-algorithm implemented in the EREW PRAM model is presented. On graphs with n vertices and m edges, it uses $O((n + m)/\log n)$ processors and runs in $O(\log^3 n)$ time. This reduces by a factor of $\log n$ both the running time and the processor count of the previously fastest deterministic algorithm that solves the problem using a linear number of processors.

A new parallel algorithm for the maximal independent set problem (MIS) is constructed. It runs in O(log4 n) time when implemented on a linear number of EREW-processors. This is the first deterministic algorithm for MIS whose running time is polylogarithmic and whose processor-time product is optimal up to a polylogarithmic factor.