Difference between revisions of "Visualization of Social Net"

From Cohen Courses
Jump to navigationJump to search
(Created page with 'This is a technical [[Category::Problem|problem]] related to one of the term projects in Information Extraction 10-707 in Fall 2010. Relation extraction broadly speaking ref…')
 
 
(16 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
This is a technical [[Category::Problem|problem]] related to one of the term projects in [[Information Extraction 10-707 in Fall 2010]].
 
This is a technical [[Category::Problem|problem]] related to one of the term projects in [[Information Extraction 10-707 in Fall 2010]].
  
−
Relation extraction broadly speaking refers to the task of relating entities present in a document. This can take on many specific forms, such as labeling the relation between two given entities, or finding all entity pairs that satisfy a relation, or even multiway relation extraction (also called [[Record Extraction]])
+
Visual representation of social networks is important to understand the network data and convey the result of the analysis [http://www.cmu.edu/joss/content/articles/volume1/Freeman.html]. Most of the softwares have besides the analytical tools also modules for network visuaization. Exploration of the data is done through displaying nodes and ties in various layouts, and attributing colors, size and other advanced properties to nodes.
  
−
==History==
+
Typical representation of the network data are graphs in network layout (nodes and ties). These are not very easy-to-read and do not allow an intuitive interpretation. Various new methods have been developed in order to display network data in more intuitive format (e.g. Sociomapping [http://en.wikipedia.org/wiki/Sociomapping]).
  
−
Relation Extraction has been studied in depth at MUC (MUC-6, MUC-7) and ACE (ACE2, ACE 2004, [[ACE 2005 Dataset |ACE 2005]], ACE 2007, ACE 2008) series of conferences and evaluations. For biomedical literature, the BioCreAtIvE II tasks have also been useful.
+
==State of the art==
 +
 
 +
Currently there are visualization tools for search, music, networks, online communities, and almost anything else you can think of. In particular, we are interested in the visualization for social network. Some of the best examples include a visualization of connections in last.fm, a visualization of relationships for youtube videos, a visualization tools for related items in Amazon etc. [http://www.readwriteweb.com/archives/the_best_tools_for_visualization.php]
 +
 
 +
In order to develop visualization software for social net, people usually use third party tools, one of the most popular tools in academia is the Prefuse toolkit (Written in Java) from University of California at Berkeley [http://prefuse.org/]. A few others are available too, however, for different purpose. For example, Flare [http://flare.prefuse.org/] is widely used for web application and GUESS [http://graphexploration.cond.org/] supports a command line based front-end. The CMU-ENCORE project [http://www.cs.cmu.edu/~encore/] currently adopted Prefuse for developing a tool for visualizing the Cross-Document Co-reference results.
 +
 
 +
==Progress==
  
−
==Details==
+
CMU-ENCORE project has been focused on this task since the summer of 2010, the overall objective is:
  
−
The most common type of Relation Extraction is binary (i.e. for two entities), and can take on one of the following specific forms:
+
* To serve as an interface to the ENCORE:ENtity CO-REference system
 +
The Cross Document Co-reference system is designed as a pipeline process of a Within-Document Co-reference process which produces chains of mentions for every document, a Cross-Document Co-reference process to cluster the chain together pair by pair and a visualization tool as the user interface to view the output of the entire system. The visualization tool currently has the following three features:
  
−
* Finding the type of relationship between given entities in text
+
1) Visualizing the graph of entities
−
Although in one sense this problem is easier than entity extraction because we only need to make one prediction instead of a vector of predictions, it is still considered harder because it requires a variety of syntactic and semantic features, both local as well as nonlocal. This problem is solved using one of the following types of methods:
 
  
−
1) Feature based methods
+
2) Visualizing the profile of entities
−
These methods extract a flat set of features from the input and then invoke an off the shelf classifier like a decision tree or a SVM.
 
  
−
2) Kernel based methods
+
3) Visualizing the connection of entity groups
−
These methods design special kernels to capture similarity between entities with complicated structures.
 
  
−
3) Rule based methods
+
As illustrated below:
−
These methods create propositional and first order rules over structures around the two entities.
 
  
−
* For a given entity and relationship, find all entities that satisfy the relationship with the given entity.  
+
[[File:Vis-ENCORE.png]]
  
−
* For a given relationship, find all entity pairs that satisfy it.
+
* To serve as an analytical tool for business intelligence or forensics purpose. Thus the interface should be able to provide evidence (the links to the documents) and serve as a entity-based document browser.
−
This problem is tackled by using a seed database of entity pairs to learn extraction patterns, which are then used to create candidate triplets (Entity1, Entity2, Relationsip). Finally, these candidates are pruned.
 
  
−
==State of the art==
+
As illustrated below:
−
In spite of the extensive research on the topic, the accuracy values of relation extraction systems in ACE evaluations still range only in the 50-70% neighborhood. Open-domain systems do even worse, and aren't usually based on very principled approaches; they contain a lot of special case-handling.
+
 
 +
[[File:Vis-ENCORE2.png]]
  
−
==Related Paper==
+
==Potential Improvement==
−
The [[RelatedPaper::Information Extraction Survey by Sunita Sarawagi]] contains more detail on this problem, and prior work to solve it.
+
The tool continues to evolve, mainly in these three different directions: (1) adding entity lifeline; (2) adding occurrence of the entity; (3) highlighting the entities of interests.

Latest revision as of 23:54, 23 October 2010

This is a technical problem related to one of the term projects in Information Extraction 10-707 in Fall 2010.

Visual representation of social networks is important to understand the network data and convey the result of the analysis [1]. Most of the softwares have besides the analytical tools also modules for network visuaization. Exploration of the data is done through displaying nodes and ties in various layouts, and attributing colors, size and other advanced properties to nodes.

Typical representation of the network data are graphs in network layout (nodes and ties). These are not very easy-to-read and do not allow an intuitive interpretation. Various new methods have been developed in order to display network data in more intuitive format (e.g. Sociomapping [2]).

State of the art

Currently there are visualization tools for search, music, networks, online communities, and almost anything else you can think of. In particular, we are interested in the visualization for social network. Some of the best examples include a visualization of connections in last.fm, a visualization of relationships for youtube videos, a visualization tools for related items in Amazon etc. [3]

In order to develop visualization software for social net, people usually use third party tools, one of the most popular tools in academia is the Prefuse toolkit (Written in Java) from University of California at Berkeley [4]. A few others are available too, however, for different purpose. For example, Flare [5] is widely used for web application and GUESS [6] supports a command line based front-end. The CMU-ENCORE project [7] currently adopted Prefuse for developing a tool for visualizing the Cross-Document Co-reference results.

Progress

CMU-ENCORE project has been focused on this task since the summer of 2010, the overall objective is:

  • To serve as an interface to the ENCORE:ENtity CO-REference system

The Cross Document Co-reference system is designed as a pipeline process of a Within-Document Co-reference process which produces chains of mentions for every document, a Cross-Document Co-reference process to cluster the chain together pair by pair and a visualization tool as the user interface to view the output of the entire system. The visualization tool currently has the following three features:

1) Visualizing the graph of entities

2) Visualizing the profile of entities

3) Visualizing the connection of entity groups

As illustrated below:

Vis-ENCORE.png

  • To serve as an analytical tool for business intelligence or forensics purpose. Thus the interface should be able to provide evidence (the links to the documents) and serve as a entity-based document browser.

As illustrated below:

Vis-ENCORE2.png

Potential Improvement

The tool continues to evolve, mainly in these three different directions: (1) adding entity lifeline; (2) adding occurrence of the entity; (3) highlighting the entities of interests.

Retrieved from "http://curtis.ml.cmu.edu/w/courses/index.php?title=Visualization_of_Social_Net&oldid=2332"