Thursday, May 17, 2007

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.

Saturday, May 5, 2007

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:

Thursday, May 3, 2007

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.