Web Mining (B659) 2006

2006-05-02T10:23:00.000-07:00

Our final results are List of names of clusters and List of urls of clusters. Code we developed can be found in here.

The lists do not themselves demonstrate success of our algorithm. We tried to find a known cluster of our personal blogs, however on the thresholding most of the their blogs are removed and we could not derive a reliable conclusion from that information.

We ran the clustering algorithm there is a one single cluster left with about 2/3 of the nodes. May be we should try to do the clustering using lesser number of blogs for better understanding about the algorithm. In the light of the final exams we had to stop our effort without without empirical justification for the tequniques we presented.

Finally few possible future work

Based on the clustering we did, pick subset of 40 000 blogs that have highest connectivity and perform clustering again

Our relatedness measure favors the high number of subscriptions in contrast to few rare subscriptions do to logarithm. May be we should compare and contrast two approaches using the samples from the collected blogs and add a refinement to relatedness measure

visualization of the communities

Come up a measure for success of the algorithm for relatedness

2006-05-02T07:25:00.000-07:00

Results

The result of the project is a dendogram of the blog nodes. We try to summerize the finding below.
The following results are such that the original graph of 40000 nodes is threshold in such a way that it is reduced to a graph of 1638 nodes. Then following are the results obtained by parsing the dendogram file that was produced.
Below is the statistics of the size of the cluster against the frequency of the clusters of that size.

Size of the Cluster	Frequency
2	168
3	62
4	14
5	1
6	2
8	1
10	1
11	1
1014	1

2006-04-24T14:29:00.000-07:00

Modifying Radicchi Algorithm to handle large connectivity graphs

The connectivity graph that we have obtained from the blogs was too densed as shown in the statistics earlier. Radicchi algorithm is an much simplfied version of the original Grivan Newman algorithm. But for a graph of over 40,000 nodes and few million edges, even Radicchi algorithm becomes computationally unfeasible. SO we have adopted few of the following optimization mechanisms and managed to bring the computation time from few weeks to little less than a day. Following are the optimizations

* Prune the connectivity of the graph by increasing the threshold of the edges. In other words remove all the edges that are smaller than a threshold value.
* Do batch elmination of edges in the Radicchi algorithm. That is instead of removing the edge with the smallest clustering coefficient, we remove all the edges which are in that small proximity which allows us to drastically reduce the computational time.

2006-04-20T07:47:00.000-07:00

Subscription count for a Feed in our data set have a power law with exponet 1.9

let x - number of subscriptions a feed has. The graph on the right is log-log plot of x against number of occurences of each x. 1 on X axis means 0=<10, 2 means 10=<20 and so on.

Note the staight line chatersrise the power law, and notice exponet is about 1.9!

2006-04-20T06:01:00.000-07:00

Construing the co-reference Graph

We collected the information about Blogs in to a database table Blogs(id,name,url,blogrolls), here Blog rolls is a # separated list of feeds the given Blog is subscribed to. As the number of feed is about 0.2 Million we can not perform a SQL join on the table, fil instruct us to load everything to memory
We go though table Blogs and create a text file with subscriptions for each Blog. The text file had a two dimensional array of integers. ith row of the array lists all the feeds, the ith Blog is subscribed to. Each feed is represented by the hash of it's name. Also we create subscription table sub(id,subid), id is the Blog id and subid is the has of the feed.
We wrote a code to load the above text file to memory. As 2341974 subscriptions are available that take about 2.3MB*4 = 9.2MB
We need count of subscriptions each feed has, we use select subcribed, count(*) from hssub group by subcribed having count(*)>1 query to store number of subscriptions each feed has as (subid,f) in a file. ith row of the file list subid and f separated by a space. The list is sorted subid.
As we need to lookup the number of frequency using subid, we load frequency data to the two dimensional integer array, each row having subid and frequency. As there are 168932 entries and that take 0.16MB*4*2 = 1.28MB. We implemented binary search on the sorted array for faster lookup.
Using subscription count for each feed and subscriptions for each Blog we implemented our algorithm to calculate the relatedness between each pair of Blogs. To represent the graph as a adjacency matrix thresholding the calculated relatedness at 150. 150 is chosen such that matrix is spare enough for clustering. To store data we use a spare matrix representation learned at scientific computing class. (matrix is represented as a two arrays iindex[?] and data[?][2], when each entry in the adjacency matrix is represented by (i,j,w), iindex[x] is the start of entries with i=x in data. w is found by matching j value in data matrix. w = data[iindex[i+x][1] where iindex[i+x][0] =j for smallest positive x ]). We implemented a search that does a lookup on i and binary search for matching j.

2006-04-18T11:27:00.000-07:00

Clustering

The size of the connectivity graph that we are dealing is too big and it simply rules out the possibility of Girvan Newman's Clustering algorithm based on Edge betweenness. Thus Radicchi algorithm was chosen as the clustering algorithm. One problem with the Radicchi algorithm is, that it was originally intended for unweighted graphs. Our Graph is a weighted graph and the weights carry the significance of the connection between the two blogs.
One suggestion from Fillipo was to extend the Radicchi algorithm to a weighted graph. If the weight of the edge was W, one option is to take a measure sqrt(2*(i-w)) as the measure for the weight and then do radicchi based on that. Above transformation is necessary because higher weight implies strong connection and we want those connections to stick around towards the end when you do the Radicchi clustering.
One other option was to do the Radicchi as if the graph was un weighted and at the time of removing the edge select the highest value by multiplying with the edge weight and then considering the highest betweenness approximation.

2006-04-09T19:48:00.000-07:00

Data Processing

We are done with the data gathering and have started the processing. But with 40000 records in the data base we can not perform a query with a SQL JOIN, which make complex SQL queries impossible . We talked with fil and he suggest try to use all the data in to the memory and do the processing. We were able to load the data about subscriptions to the memory and currently working on creation of the graph.

Algorithm

After the discussion with Fil this is our revised algorithm. We groups feeds as private Blogs and public Blogs, in this project we are making an effort to derive the community structure from the blog-roll of private blogs. We plan to create a co-reference graph for the private blogs and perform a clustering algorithm the created graph.

Our graph creation is based on two heuristics, first we assume if two blogs have a subscribed to same feed they are related to each other. Second, we take in to account that if Blogs A and B are subscribed to Slashdot, that does not imply a strong relationship, however if two Blogs are subscribed to another Blog which has just five total subscriptions, that possibly means a stronger relationship.

To model this fact, we calculated the weighted co-reference graph from the subscriptions data using following formula.
Let SUB (A AND B), be subscription both A and B share. Let P(x), be probability that feed x is selected if Blog C add blogrolls randomly.

We use self information, log(1/P(X)) as defined by the information theory to approximate the information provided by each feed .

2006-04-04T07:26:00.000-07:00

I am collecting information about the public blog subscriptions from set of personal blogs. The code is still running adding subscriptions to the data base. So far 11349 persoanl blogs has subscribed to 203462 public blogs, which means about 20 subscriptions per blog. Here are few statistics

Public Blogs

blogs have more than 100 refernaces 843/203462
blogs have more than 75 refernaces 1205/203462
blogs have more than 50 refernaces 1836/203462
blogs have more than 32 refernaces 2954/203462
blogs have more than 16 refernaces 6089/203462
blogs have more than 8 refernaces 11842/203462
blogs have more than 4 refernaces 18281/203462
blogs have more than 3 refernaces 18281/203462
blogs have more than 2 refernaces 39378/203462
blogs have more than 1 refernaces 65985/203462
blogs have 1 refernaces 137477/203462

Personal blogs

having >5 blog rolls 10825/11349
having >10 blog rolls 10064/11349
having >20 blog rolls 8466/11349
having >30 blog rolls 7121/11349
having >50 blog rolls 5997/11349
having >100 blog rolls 2447/11349
having >200 blog rolls 800/11349
having >400 blog rolls 800/11349
having >1000 blog rolls 26/11349

Note there are 26 personal blogs that have >1000 subscriptions!!

2006-04-03T18:41:00.000-07:00

We have make a mistake on naming the graph we plan to analyze. Our document said we are analyzing a co-citation graph. But It should be co-reference graph. Our heuristic is if two blogs subscribed to same feed, there have some level of smiler interests.

2006-04-03T17:05:00.000-07:00

We have been reading about the related publications to our project. Among them we find following very interesting

Finding "the life between buildings": An approach for defining a weblog community by Lilia Efimova
Tomographic Clustering To Visualize Blog Communities as Mountain Views by Belle L. Tseng,Junichi Tatemura,and Yi Wu
NusEye: Designing for Social Navigation in Syndicated Content by Azzari C. Jarrett, and Brian M. Dennis

Even though not directly related, following are few interesting papers

Conversations in the Blogosphere: An Analysis "From the Bottom Up" Susan C. Herring, Inna Kouper, John C. Paolillo, Lois Ann Scheidt, Michael Tyworth, Peter Welsch, Elijah Wright, and Ning Yu
Power Laws, Weblogs and Inequality by Clay Shirky
On Webfeed Aggregators and Social Navigation Brian M. Dennis
Audience, structure and authority in the weblog community by Cameron Marlow
The EigenRumor Algorithm for Ranking Blogs by Ko Fujimura, Takafumi Inoue,and Masayuki Sugisaki
STRUCTURE AND EVOLUTION OF Blogspace By RAVI KUMAR, JASMINE NOVAK, PRABHAKAR RAGHAVAN,
AND ANDREW TOMKINS
How to search a social network by Lada Adamic and Eytan Adar
Discovering Important Bloggers based on Analyzing Blog Threads by Shinsuke Nakajima, Junichi Tatemura , and Yoichiro Hino
Implicit Structure and the Dynamics of Blogspace by Eytan Adar, Li Zhang, Lada A. Adamic Rajan, and M. Lukose

We decide to process the downloaded blogs from the data base itself. We have develop a code to extract the blog-rolls from the data base entries and create a new table that shows the subscriptions for each blogs. Right now we are working on following.

Code to build co-citation graph in the data base tables
Code to gather statistics about blogs from the data base tables and provide statistical analysis about blogs
Code to do clustering

As a method of evaluating the results of the clustering we decided to compare resulting groups against groups derived from the subscription (spare graph which we originally plan to analyize). As the subsriptions between private blogs suggest stronger connections among blogs, we expect subscription groups to be included in clustering groups.

2006-03-17T13:21:00.000-08:00

We have finish developing the Blog crawler and start collecting for the Blogs. By the time of writing the crawler is running and have collected 17164 Blogs.

The Blogs crawled so far seems loosely connected and the Blog graph consist of number of loosely connected components. So we might be able to analysis connected component by component without handling 50 000 Blogs at once.

Right now we are reading about work already done to identify the communities in personal Blogs.

2006-03-09T07:27:00.000-08:00

Quick update, more detai will follow soon.

We decide to use the approximation of the GN (Girvan and Newman) algorithm by Filippo at el* for identifying the communities.
Now our crawler is working and able to crawl pages successfully, Chathura is working on writing data base layer to save crawled data in the data base.
We asked fil about Graph Analysis tools, he give us a list. We prefer a java tool but do not decide on specific one yet.

* Defining and identifying communities in networks Filippo Radicchi *, Claudio Castellano , Federico Cecconi , Vittorio Loreto , and Domenico Parisi

2006-03-02T09:58:00.000-08:00

We decided on the high level architecture for the Blog crawler. The crawlers operations can be iterated out as follows.

1. Starts with subscription pages of the Bloglines
2. Crawl each Blog subscribed to the subscription page
3. For each crawled Blog we store the Blog-Rolls for the Blog and add the subscribed Blog URLs to Blog frontier
4. We do this until the Blog frontier is empty

We took following design decisions

1. We use a Distributed Queue developed by Chathura as the Blog frontier
2. We uses a MySQL data base to store the data about crawled Blogs and Blog-Rolls for each Blog.
3. We uses the data base to store the visited Blogs, and keep a local hash-map in memory to fast access. The data base protect data from losing in case of system failure.
4. We uses Apache Commons HTTP Client (http://jakarta.apache.org/commons/httpclient/)
5. We uses HTTP Parser (http://htmlparser.sourceforge.net/) to filter the Blog-rolls and subscription URLs from Blogs

We have done following steps in last two weeks

1. Step up a MySQL database, and design the tables
2. Set up a svn repository in http://www.cvsdude.org/, our code is available in the svn repository
3. Writing the code to fetch and parse the Blogs,
4. Chathura is working on the database encapsulation layer for the data
5. We have initial skeleton of the crawler, which fetch the Blogs, parse them and print the data to the screen. We are working on the saving the information on the data base and making the Blog frontier persistent.

We are yet to decide on the finer detail about how the Blog analysis is to be done, we plan to finish the data gathering steps and then start on the data analysis steps.

2006-03-01T17:58:00.000-08:00

We decided on the high level architecture for the Blog crawler. The crawlers operations can be iterated out as follows.

Starts with subscription pages of the Bloglines
Crawl each Blog subscribed to the subscription page
For each crawled Blog we store the Blog-Rolls for the Blog and add the subscribed Blog URLs to Blog frontier
We do this until the Blog frontier is empty

We took following design decisions

We use a Distributed Queue developed by Chathura as the Blog frontier
We uses a MySQL data base to store the data about crawled Blogs and Blog-Rolls for each Blog.
We uses the data base to store the visited Blogs, and keep a local hash-map in memory to fast access. The data base protect data from losing in case of system failure.
We uses Apache Commons HTTP Client (http://jakarta.apache.org/commons/httpclient/)
We uses HTTP Parser (http://htmlparser.sourceforge.net/) to filter the Blog-rolls and subscription URLs from Blogs

We have done following steps in last two weeks

Step up a MySQL database, and design the tables
Set up a svn repository in http://www.cvsdude.org/, our code is available in the svn repository
Writing the code to fetch and parse the Blogs,
Chathura is working on the database encapsulation layer for the data
We have initial skeleton of the crawler, which fetch the Blogs, parse them and print the data to the screen. We are working on the saving the information on the data base and making the Blog frontier persistent.

We are yet to decide on the finer detail about how the Blog analysis is to be done, we plan to finish the data gathering steps and then start on the data analysis steps.

2006-02-20T18:18:00.000-08:00

We discuss with Fil the Terms of Service of the bloglines, and fil says it should be ok and we should go ahead. Also we decide to use random waiting with a period of 60 seconds to crawl the bloglines site.

We are planning to use a MySql server to store the information from the crawling. We have setup a MySQL server. I am working on a code to extract the links from the bloglines pages.
--Srinath

2006-02-14T20:09:00.000-08:00

Based on the feedback for the proposal we choose a new topic, the basic idea is to cluster the bloglines blogs. Here is our proposal. We have submit the a new proposal.

Mining for Blog communities

Personal Blogs gives rise to interesting social networks. When we consider a Personal blog as a vertex of a graph, there are two types of edges that are connected to that particular vertex. Given a particular blog X;

Subscriptions to the blog X
Blog X owner's Subscriptions

Apart form this there are subscriptions are pointed to popular news feeds which could potentially unveil information about the user. In this project we try to analyze the connectivity of public blogs at www.bloglines.com to identify the communities and to observe the interests of the groups based on the public
news feeds they refer to. The information will be mined at the blogs of individuals starting form seeds harvested by querying the subscribers to popular news feeds. Starting form these seeds the system will identify and build blog connectivity graph which would be a directed graph in which the vertices would represent the individual bloggers and the edges would represent the subscriptions to blogs. In other words the If A has subscribed
to B's blog then (A, B) would be a directed edge.

The analysis is geared towards

Community identification
Identifying meta-groups of similar interest within a community by filtering the individuals that has subscribed to popular feeds of same or similar interest.
Given initials seeds that would contain blogs of individuals that share same interest or may be interested in same area of technology, identify a community that consist of individuals that share the same interest with high probability.

Tasks

Identifying seed blogs - This would be based on either harvesting the blog by
going to subscribers to popular news feed or by user input depending on the use case.
Crawling the blogs - Involves crawling the blogs based on initial seeds and
building a frontier by analyzing already crawled blogs.
Social network analysis using graph algorithms - Involves connectivity graph
analysis and graph overlap analysis based on use case.
Visualization and filtering of communities -Using a visualization package to
visualize the output graph and to emphasize the relationships and clusters/communities identified.

Note: We have looked in to the robots.txt file at www.bloglines.com and we can extract necessary information without violating it.

2006-02-05T07:29:00.000-08:00

I come across a Grpah analysis framework called JUNG
(http://jung.sourceforge.net/). If any of you plan to do social network analysis
it might be hepful. And it is very well documented !!

I did a litte programme to parse the message borad and build a network based on
the dicussions took place on the message board. Here is the visualization of it with JUNG!

2006-01-31T20:01:00.000-08:00

Praposal

Comparison of research community derived from co-author networks with cluster of related publication derived from citation graphs

Group : Srinath Perera and Chathura Hearth
Blog : http://cs-b659.blogspot.com/

In this project we plan to apply existing community identification algorithms to co-author networks and citation-graphs constructed form research publications of a particular domain. In identifying co-author networks, we consider two authors are connected if they have co-authored a publication. Thus this author community graph will consist of author nodes and the vertices of the graph will represent a value that represents the publications that they have co-authored. Secondly, in the citation graph of the publications of the domain in concern, the nodes represent the publications and the vertices will represent the citations.

Both the cluster extraction techniques will be based on the social network analysis techniques that have been developed by previous research. The identification of communities expected to result in following communities.

Community of authors - Communities in the first graph have a likelihood of identifying research communities and further they will represent research groups that are collaborating in particular area of research.
Cluster of related publications - Communities in the second graph will identify clusters of research papers belong to a one broad research area or a meta-research area within a broader research area.

Once the two graphs are constructed we can identify the authors from the clusters of relation publications and compare the relationships between two types of author groups. The final outcome of the project would be to observe the co-relation between the two different set of information extracted from academic publications from a particular domain and to identify meta research groups within a given research area, and the topics they are working on.

Task List.

Decide and obtain the publication set on which the network analysis will be performed
We have not pinpoint algorithms used to identify the communities in the each case, but for the co-author graphed we consider the approach presented by Ebel, Davidsen and Bornholdt [1] is a possible candidate and for co-citation graph we plan to pick one of the algorithms from refernaces [3], [4] or [5].
We are thinking about using a focused topic like Web Services under computer Science and gather all related Papers.
If time permitting we would provide a GUI to visualize the communites we identified in the analysis

References

[1] H Ebel, J Davidsen, S Bornholdt, “Dynamics of Social Networks”

[2] Yuan An,Jeannette Janssen,Evangelos E. Milios, “Characterizing and Mining the Citation Graph of the Computer Science Literature”

[3] Gary William Flake, Steve Lawrence, C. Lee Giles, Frans M. Coet, Self-Organization and Identification of Web Communities

[4] Filippo Radicchi, Claudio Castellano, et al “Defining and identifying communities in networks Community structure in social and biological networks“

[5] M. Girvan and M. E. J. Newman “Co-authorship networks and patterns of scientific collaboration”