MDS graph with Connotea data by using GGobi.
Wednesday, April 23, 2008
Wednesday, February 13, 2008
Status report for 02/07/2008 to 02/13/2008
I have been doing tag analysis to find underlying relationships between tags, users, and resources in folksonomies. I think there are possibly two different approaches: i) frequency analysis based on resource vectors spanning over the term space and ii) graph-based analysis based on tag graphs.
In the frequency analysis, we can use Principal Component Analysis(PCA) or Independent Component Analysis(ICA). Similar approaches have been done in the field of IR. An example can be found in here, where PCA and ICA were used for tag-advertising matching.
With PCA and ICA, I produced the following figures:
(a) PCA with Tag-graph
(b) ICA with Tag-graph (number of component = 3)
It is very interesting that we can see some tag relationships (or tag clusters) in both two pictures but reasonable interpretation is not so easy to get. I think it's a good starting point to cluster terms for extract meaningful information. I will keep working on those graph.
As for the next step, I'm going to do analysis with graph-based methods.
Wednesday, December 19, 2007
Status report for 12/13/2007 to 12/19/2007
1. Listing up papers for Oral Qual.
I've been making a reading list for oral qualify exam. The focus of my oral exam will be (1) Folksonomies and Web 2.0 architecture, (2) Machine Learning, and (3) Multicore and parallel programming of machine learning algorithms.
2. Paper reading - HMM
I've been reading a paper about Hidden Markov Models:
L. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proc IEEE, vol. 77, pp. 257-286, 1989.
A short summary is as follow:
-. HMM: A Markov chain with hidden states. HMM can be used to guess a transitions between hidden states based on the observation
-. The basic 3 problems in HMM: (a) Given a HMM model, compute probability of an observation sequence, (b) Given the observation sequence, guess a probable state sequence, and (c) Adjust HMM model parameters to maximize P(Observations|HMM Model)
-. Viterbi Algorithm can be used to solve the problem of type (b)
-. Expecation-Maximization algorithm can be applied to (c)
Wednesday, November 14, 2007
Status report for 11/08/2007 to 11/14/2007
I've been reading a paper about ranking in folksonomy, called FolkRank, proposed in Trend detection in folksonomies, Information Retrieval in Folksonomies: Search and Ranking.
FolkRank is based on well-known PageRank algorithm used in Google (The Anatomy of a Large-Scale Hypertextual Web Search Engine and The PageRank Citation Ranking: Bringing Order to the Web).
In a nut shell, the basic idea of PageRank is that a page is important if there are many pages linking to it. This can be formulated by the following matrix equation:
R(u) = c \sum R(v)/N or R(u) = c \sum R(v)/N + cE(u)
where
u is a web page and v is a page referring u,
R(u) and R(v) are PageRank of u and v repectively,
N is a number of all links in page u, and
E(u) is called a source of rank.
Folksonomy can also be represented as a graph by using the similar concept of PageRank but a few exceptions:
- Folksonomy graph is undirected, while web graph in PageRank is directed.
- Nodes are heterogeneous and the graph is triadic, while in PageRank the nodes are homogeneous.
I think it's a good start to begin with applying PageRank algorithm to folksonomy recommendation system. For this purpose, I'm planing to dig into more details on the PageRank algorithm and find some sample code for better understand.
Thursday, November 08, 2007
Status report for 11/01/2007 to 11/07/2007
1. I made a reading list about folksonomy at my CGL blog or del.icio.us. I will update the list frequently by adding related articles.
2. Characteristics of Folksonomy Network
The folksonomy networks show the following characteristics:
a. Small-world Network
Almost similar with a random network but having much larger clustering co-efficient factor. I.e., Small shortest path but a larger clustering coefficient.
b. Scale-free Network
A scale-free network is a network in which any two nodes can be connected no matter what the system size is. This is because there is a node called "hub"which is a highly connected node than any others. In folksonomies, popular keywords can act like this hub and thus the network shows scale-free network properties.
A scale-free network shows the following rules:
(1) Power law : Degree distribution follows the Yule-Simon distribution, which is called a power law: P(k) ~ k^(-r), where k is a degree of connectivity of a node and P(k) is it's probability
(2) Preferential Attachment : A way to build a scale-free network. The idea is to make a connection with a more connected node.
3. Next step
a. Build a simple graph by using CITEAM tag data
b. Find some algorithms about recommendation
Sunday, November 04, 2007
Reading list about folksonomy analysis
(Also available at http://del.icio.us/yyalli/folksonomy)
Formal Model, Graph
- The Complex Dynamics of Collaborative Tagging, HT 07
- Network Properties of Folksonomies, WWW 07
- Mining Association Rules in Folksonomies, Data Science and Classification
- Ontologies are us: A unified model of social networks and semantics, Web Semant. 5, 1 (Mar. 2007)
- Folksonomy as a Complex Network
- Trend detection in folksonomies, LNCS, 2006
- A Social Networking Model of a Web Community,
Semantic Web
Pattern, Structure
- Towards Better Understanding of Folksonomic Patterns, HT 07
- HT06, tagging paper, taxonomy, Flickr, academic article, to read, HT 06
Recommendation, Ranking, Trend
- Tag Recommendations in Folksonomies, LNCS, 2007
- Trend detection in folksonomies
- Recommending Smart Tags in a Social Bookmarking System
- Information Retrieval in Folksonomies: Search and Ranking
- Harvesting social knowledge from folksonomies, HT 06
Tag Generation
PageRank
- The Anatomy of a Large-Scale Hypertextual Web Search Engine, Sergey Brin and Lawrence Page, 1998
- The PageRank Citation Ranking: Bringing Order to the Web, 1998
Clustering (referred from Filippo Menczer's class material)
- Web Page Recommender System based on Folksonomy Mining for ITNG ’06 Submissions, ITNG '06, 2006
- Finding related pages in the World Wide Web, Computer Networks, 1999
- Self-Organization and Identification of Web Communities, IEEE Computer, 2002
- Finding replicated Web collections, ACM SIGMOD '00, 2000
- Community structure in social and biological networks, PNAS, 2002
- Defining and identifying communities in networks, PNAS, 2004
Learning and Classification (referred from Filippo Menczer's class material)
Wednesday, October 10, 2007
Status report for 10/04/2007 to 10/10/2007
I have been searching articles about folksonomies in the Internet. Among them the followings are useful to understand:
- Folksonomies - Cooperative Classification and Communication Through Shared Metadata : Pros and cons about folksonomies. Future research areas.
- Ontology of Folksonomy : Roles of ontologies and folksonomies.
Some researches about folksonomy applications by using machine learning algorithms.
- Visualizing Folksonomies using Machine Learning Algorithms
- Learning from a Visual Folksonomy: Automatically Annotating Images from Flickr
- Optimizing web search using social annotations
I have also started reading an introductory machine learning book, "Introduction to machine learning" by Ethem Alpaydin. During the next week, I will search and read more papers about folksonomies and machine learning.
Thursday, June 14, 2007
Status Report for 06/07/07 to 06/13/07
1. Hostnames
NWS’s memory service, which provides memory service to store NWS sensors’ data, saves data based on NWS sensors’ hostnames. (A hostname is a system name returned by gethostname or ‘hostname -–fqdn’) This can be problem when a master and sensors installed in different clusters and a sensor’s hostname is not a public domain name, i.e., internal hostname. For example, BigRed's hostname is not for publicly accessible from the Internent, rather hostnames are for only internal uses. In this case, NWS’s information extractor, nws_extract , can not show correct data to a user. If the memory service is in the same cluster with sensors, it will be ok but no other sensors outside clusters will be allowed.
2. Manager nodes and computing nodes
NWS’s bandwidth measurement may be incorrect depending on cluster’s topology. For instance, NCSA’s TeraGrid cluster consists of four manager nodes, which have all public hostnames and thus can be accessible from the Internet, and hundreds of computing nodes, whose hostname is not known unless submitting a job. To measure bandwidth before knowing which node will run a job can be difficult. To overcome this possible problem, knowledge on a cluster’s topology or managing policy will be required, if possible, by contacting a help desk.
Thursday, June 07, 2007
Status Report for 05/31/07 to 06/06/07
I've installed a NWS client in a few TeraGrid clusters and in my local machine to measure network bandwidth information between them. To sum up, we need to run the followings for a master node and a client node
a. Mater node
nws_nameserver
nws_memory
nws_sensor
b. Client node
nws_sensor
To start measuring, we need to submit the following command:
start_activity -f file_name name_server
To extract measured values, type the following:
nws_extract -N name_server -f time,measurement band from_node to_node
Here is some outputs for network bandwidth:
## Units: Megabits/second
## E.g.,
## 1181197165 (<= This is time) 6.148710000(<= This is bandwidth, Megabits/second)
## Network bandwidth between a.ufo.edu and b.ufo.edu
$ nws_extract -N nameserver.ufo.edu -f time,measurement,source,destination band a.ufo.edu b.ufo.edu
Time Measure Source Destination
1181197165 6.148710000 a.ufo.edu b.ufo.edu
1181197285 6.142370000
1181197405 6.135040000
Thursday, May 31, 2007
Status Report for 05/24/07 to 05/30/07
I’ve finished updating STFILTER and Analyze_Tseri service to process multiple GPS stations at the same time. Now multiple stations data is shown in one graph. The overhead, I guess, may be linearly increased as the number of stations is increased. However, for time being, it looks fine a few stations. More details will be measured later. In addition, there are a few minor bugs, which will be fixed soon.
Wednesday, May 23, 2007
Status Report for 05/17/07 to 05/23/07
I’ve been updating STFILTER and Analyze_Tseri web service to make the system deal with multiple sites (Previously only single site can be supported). The implementation is almost done except displaying multiple graphs by using BFO library. Since the output from analyze_tseri application is a union of multiple outputs of single execution with a single site, the graph should be multiplied or multiple graphs should be displayed in one graph by merging them.
2. Network Bandwidth Information
Yili preferred to install NWS server/client in the nodes of TeraGrid. So, I’m making a list of nodes to install NWS client and server. There might be restrictions using a special port or network traffics. I will keep posted when I have problem.
Thursday, May 17, 2007
Status Report for 05/10/07 to 05/16/07
During the last week, I’ve been updating STFILTER portlet and Analyze_Tseri to make the system to deal with multiple sites. To make sure correct operation, I started with making a test case to run standalone tseri_analysis program. Now, I’m updating STFILTER portlet and Analyze_Tseri webservice and will complete in the early of next week.
2. Network Bandwidth Information
I’ve been looking at again NWS (Network Weather Service) to find out how to get network bandwidth information in Teragrid from NWS but it seems like there is no publicly available method to share. Although we can install NWS server/clients for each node for testing purpose, it will suffer from low scalability.
Wednesday, May 09, 2007
Status Report for 05/03/07 to 05/09/07
During the last week, I’ve been updating STFILTER portlet by using Db4o to support project management feature. Now STFILTER portlet can save query parameters as a project and reload later. I’ve also updated Analyze_Tseri service by changing interface parameters to receive GRWS URL as an input. Thus, STFILTER portlet doesn’t need to send data as String type. Instead, only GRWS URL is enough. Analyze_Tseri will download by connecting to GRWS service. In the future, Analyze_Tseri will be updated to query GRWS directly with given parameters. The next thing to do is to provide support for processing data from multiple stations.
Wednesday, May 02, 2007
Status Report for 04/26/07 to 05/02/07
1. Problems in implementing custom serializer/de-serializer of analyze_tseri service. Making webservice exchange user-defined complex type has some errors.
2. Lock/Un-lock features. I have lock related errors in using Db4o. Currently, I disabled lock features to prevent such errors. But, I don’t know which is better way for STFILTER portlet.
3. Deleting temporary files. Analyze_tseri web service is now saving user’s input and output under a directory in a way a user can download files directly through http protocol. However, at some point, such files should be deleted to save disk spaces. I didn’t decide yet when and which is the best way to do that.
Wednesday, April 25, 2007
Status Report for 04/19/07 to 04/25/07
- Lock related errors in using Db4o. Currently, I disabled lock features to prevent such errors. But, I don’t know which is better way for STFILTER portlet.
- Analyze_tseri web service is now saving user’s input and output under a directory in a way a user can download files directly through http protocol. However, at some point, such files should be deleted to save disk spaces. I didn’t decided yet when and which is the best way to do that.
Wednesday, April 18, 2007
Status Report for 04/012/07 to 04/18/07
I’ve updated STFILTER portlet by adding more time series parameter filters. In addition, time series analysis service (analyzeTseri) and STFILTER portlet has be updated with easy installation procedure so that most user dependent system settings can be done in installation step As for the next step, I will add project management features in STFILTER portlet.
2. Network Weather Service
I’m still searching for how to get list of hosts served as Network Weather Service hosts. There is no open information to list up such hosts. I think we need to ask either TeraGrid help desk or Network Weather Service development team
Wednesday, April 11, 2007
Status Report for 04/05/07 to 04/11/07
I’m still updating both analyze-tseri-exec webservice and STFILTER portlet to work with addition parameters for time series analysis. Although no technical difficulties yet, it takes some time to make them more general as they are sharing same code in many cases. I will finish this update in a few days. After updating, I will modify the project management part of STFILTER portlet.
2. TeraGrid 07 final paper submission
I’ve been updating TeraGrid 07 paper for camera ready, co-worked with Mehmet and Marlon. The final due is April 12th.
3. Network Weather Service
I sent an email to NWS’s developer mailing list (nws-dev@cs.ucsb.edu) to query about any possibility to get network bandwidth service but haven’t get any reply yet. To prepare worst case, I think I need to find other way to get such information.
Wednesday, April 04, 2007
Status Report for 03/29/07 tto 04/04/07
I'm updating analyze_tseri web service to use a bean as an input parameter. Accordingly STFILTER portlet will be updated soon.
As for the next step, I'm planning to upgrade STFILTER portlet as follow:
a. Adding more options on filter parameter.
b. Using property file, instead of web.xml or portlet.xml
c. Modifying project management
d. Fixing some bugs when clicking "edit" mode button.
2. Network Weather Service
After installing nws package from NWS website, I found a NWS command for extracting inter-machine bandwidth and latency measurements as follow:
$ html-hosts -N nws.cs.ucsb.edu sperm.cs.ucsb.edu beluga.cs.ucsb.edu
| Source machine | Destination machine | ||||
|---|---|---|---|---|---|
| sperm.cs.ucsb.edu | beluga.cs.ucsb.edu | ||||
| sperm.cs.ucsb.edu | bw forecast error lt forecast error | - - - - - - | 86.10412000 86.10059000 1.759016353 0.429000000 0.370000000 0.091088105 | ||
| beluga.cs.ucsb.edu | bw forecast error lt forecast error | 85.42371000 85.52822000 4.072307805 1.648000000 1.702000000 0.320489947 | - - - - - - | ||
However, I haven't found yet if I can use this command more generally, for example, in TeraGrid clusters. It seems like if I know a name server of a cluster, it will be possible to get network bandwidth information. But, I don't know how I can get list of such name server. I will dig into that more.
Thursday, March 29, 2007
Moab dashboard or memejob portlet configuration
a. Copy memejob-portlet.war to $CATALINA_HOME/webapps
b. Modify ./WEB-INF/portlet.xml as follows:
Basically, by using memejob-portlet, memejob can be send to multiple sites as shown in "hostnames" parameters. If you don't need multiple site, only one host name in "hostnames" parameter will be enough. The other values should be set with similar way.
-. hostnames : list of hosts to submit meme job. Comma separated and no space between them.
-. batchhostnames : list of hosts names for batch job submission
-. commandset: list of meme execution file path. The order must be the same with list of hostnames
-. pathset : list of path env. The order must be the same with list of hostnames.
-. gridftpservers : list of ftp servers for each host shown in hostnames.
2. moab-dashboard
a. Copy moab-dashboard.war to $CATALINA_HOME/webapps
b. Modify ./WEB-INF/portlet.xml as follows:
moab-dashboard portlet can support executing moab command in multiple sites. You can specify either list of sites in "hostnames" or one site if you want only support only one site.
-. hostnames: list of host names
-. commandset: list of path of moab command. The order should be same with hostnames.
-. checkjob: list of path of 'checkjob' command.
3. Displaying in OGCE portal
When the deployed portlet is shown as a non-portlet web application in “Adminitration” tab of OGCE, we can change it as a portlet application as follow:
a. In “Administration” tab, type “moab-dashboard”(or memejob-portlet) in “Deploy new portlet webapp” and click “Deploy” button. If successful, you can see “moab-dashboard” in “Portlet web applications” section. You may need to refresh the screen by visiting other tab or re-logging.
b. Go to “Welcome” tab, check “moab-dashboard”(or memejob-portlet) in “Configure group membership” and click “Save” button. You can see a new tab named “MOAB Dashbarod”(or “Meme job”)
Wednesday, March 28, 2007
Status Report for 03/22/07 to 03/28/07
I have made AnalyzeTseriService more self-contained that the service can get environmental parameters as well as array of time series data. Thus, STFILTER application can query more dynamically from the AnalyzeTseriService service. However, the better way is to make the service receive a bean as an input parameter so that a client only needs to send only a bean.
During the last week, I have been busy in doing some class project. I'm planning to upgrade STFILTER portlet and investigate on Network Weather Service.
