Visualizing social interactions

Everyday we are part of multiple communication graphs (emails, tel calls, blogs, IP traces) and play different roles there. What is the structure in them, and what are suitable signatures we display? A recent study of usenet groups provides some answers.

Virtual Network Analysis

As a part of the DyDAn seminar series, Victor Asal and Karl Rethemeyer gave a talk on Empirical and Virtual Terrorist Networks. The talk was about determining and analyzing factors indicating how dangerous a terrorist group is. Using statistical analysis, the speakers showed that factors such as connectivity of the organizations and their ideology have strong correlations with their lethality. They supported their claims using both historic terrorist data from MIPT Terrorism Knowledge Base and that extracted from websites of terrorist organizations. The speakers emphasized on the potential of monitoring web-based interactions (possibly hidden or disguised) between terrorists and terrorist groups for predicting and preventing future attacks.

The speakers had an impressive visualization of the interactions between 200 terrorist organizations in the form of a graph. This graph was packed with information like lethality and of the organizations, religious-orientation, known and predicted alliances between the groups. Currently, this information is manually created by painstaking data compilation. It remains a challenge to automate this process, or provide some automated assistance to more easily compile the information.

Nature of Blogs

There are many different blog publish/ponder services out there (myspace, blogger, xanga, livejournal, facebook, friendster, etc); they seem to attract and foster different types of communities. Studies of the bloggers in these different services reveal inherent properties: people tend to have different profiles in age and geographic location, connections within one blog service are more extensive than across services, and there is a lot of information that relates to services other than blogs. Details at:

• A web2.0 journal entry.
• Intl Conf on Weblogs and Social Media (ICWSM 07) paper from DyDAn.
  
• A map of blogosphere.
  

Analyzing Semantic Graphs

A lot of data analysis work has studied various aspects of graph structured data (comprising entitites, or nodes, with some pairs linked together by edges). But a simple graph is often insufficient to capture the complex relations seen in practice: although connectivity within a computer network can be represented by a graph, there are many different kinds of nodes (computers, routers, switches) and different kinds of links between them (DSL lines, fiber links etc.). Consequently, the idea of "semantic graphs"-- graphs which include this richer information on types of entities and different links between them--are of increasing interest. Moreover, in practice these graphs are not static, by changing over time as new connections are formed or discovered, leading to dynamic semantic graphs.

Back in March, Tina Eliassi-Rad visited DyDAn and talked about some of her recent work on Dynamic Semantic Graph analysis. Many natural questions she introduced lead to concrete research problems:

• How to visualize a semantic graph, and adequately convey the different relationships therein?
  
• How to find paths of connections in semantic graphs, and determine if these are significant?
• How to efficiently find instances of a particular subgraph within a large Semantic Graph (with wildcard matching, etc.)?
• How to find patterns or anomalies within the data, indicating unexpected relations or features to investigate in more detail?

She talked in detail about the problem of learning functions within the graph. The key insights are to be able to combine ideas from both machine learning and graph theory, rather than try to reduce to one alone. The topological features of a graph are important features to provide for a learning algorithm. Fully incorporating the time-dynamics remains a major challenge.

A recent workshop at DyDAn also studied the problems of semantic graphs from a variety of perspectives -- the slides are available from the workshop website.

Privacy preserving data analysis

Theoretical computer science formulated the basic notions of how to analyze data without revealing any more information than is necessary for the analysis (more or less). The bottomline is a lot of computations can be done in that manner, although with some computational overhead. A nice set of algorithmic tools have also been developed for specific problems. A collection of papers can be found here. These techniques are now being adopted to other communities, eg.,

• databases, see eg., here.
  
• networking, see eg., here by Matt Roughan and Yin Zhang.
  

There is a real need to formulate and address problems with social network analysis using privacy preserving methods.

Netflix Prize and Privacy

Netflix has released a sample of data publicly and has offered a significant prize to predict peoples' rating for movies better than their baseline solution. The data comprises customers and their ratings of movies and the times the ratings were posted. Customers are anonymized, by removal of immediately identifying information.  Some noise is introduced by some perturbations of the data, and a claim that only a small amount of information from any one customer is included.

In a recent study, the authors experimentally evaluate the following: for each customer c and k of their movie rating and times given, determine the number N(c,k) of other customers who posted "nearly" same ratings at "nearly" same times for these movies? The argument is that for small k, if N(c,k) were small, then customer c can be disambiguated with some effort or knowledge.

The paper appears to be in a preliminary form. From a theoretical point of view, there are nice problems here. Can we propose a probabilistic model for customer ratings and derive an estimate for N(c,k)?

What blogs reveal?

What blogs reveal about one is a deeply technical or deeply philosophical question. They have attracted a lot of interest academically. In computer science, people have abstracted problems based on text attributes, analogies with epidemiology on the spread of "memes" through blogs, studied graph properties and so on. In doing such study, one becomes quite familiar with the literature from people in CS and related fields, but also start to learn how they are approached by other fields such as sociology and psychology. An example is a study on gender, identity and language in teenage blogs, done a couple of years ago. A long (exhaustive?) list of blog related research from all discplines appears on the homepage of a blogging researcher / researching blogger.

Privacy and Confidentiality

Stephen Fienberg gave a nice talk with a statistical perspective on data privacy at the kickoff meeting of DyDAn. He introduced the need for privacy awareness in data handling, and some of the hazards if it is ignored (slides are here). He spoke in detail about giving bounds on cells of a contingency table given certain marginals; this was based on his PNAS paper. He also publicized a upcoming WWW 2007 paper by Backstrom, Dwork and Kleinberg on theoretical analysis of privacy in social networks or lack thereof. Both these papers raise a lot of fascinating questions, and lead to a lot of scope for further study, in statistics and theoretical computer science.

DyDAn Official Launch

DyDAn kicks off officially on Fed 26th with a series of talks. There will be talks by Director of Research Futures in DHS, Deputy Director of Inst for Sc. Computing Research at LLNL, and Stephen Fienberg from CMU. Privacy in data analysis is obviously an important theme. In database research community, there is growing emphasis on this. See the 8 papers in 2 revelant sessions at ICDE 2007 and more are forthcoming in SIGMOD and PODS 2007.

RVACs

One of the key aspects of data analysis is visualization. DHS in collaboration with the National Visualization and Analytics Center (NVAC) has established Regional Visualization and Analytics Centers (RVACs) to provide both research expertise and training and education programs. The research program of the RVACs sounds very exciting, in particular, since they include careful study of collaborative decision making methods.