03-60-569 Semantic Web 2011

There are more office hours on Dec 9 11:00am -2pm.

Instructors

• Email: jlu at uwindsor
• Phone: 3786
• Office: Lambton Tower 5115

Course Overview

Time and Place

• Lecture time and place: Tuesday and Thursday 10:00-11:20 ER 3119.
• Office hours: Tuesday/Thursday 11:30-12:30. More office hours are provided on Monday and Wednesday 12:00-2:00 .
• Final exam: Saturday Dec 10, 08:30.

Schedule

• Week 1: Introduction (ppt)
  Readings: Chapter 1 of SW book.
• Week 2,3,4: Lecture slides: Web search (Web search basics webchar.pptx, Near duplicate, Link analysis and spam, web crawling)
  • Matlab program for graph example graphExample.m
  • Plotting power law distribution powerLawPlot.m
  • Illustration of PageRank algorithm in Matlab pagerank.m
  • Readings: Chapter 19, 20, and 21 of IR, and the papers in the following table.

    topic	Papers		Time
    Search engines	Steve Lawrence, C. Lee Giles, Searching the WWW , Science 1998. Steve Lawrence; C. Lee Giles (1999). "Accessibility of information on the web". Nature 400 (6740): 107.	Mahmoud	Nov 3
    SW tools	Semantic web parser(s), Jena	Bryan	Nov 8
    Web as graph	R Albert, H Jeong, AL Barabasi - 1999, Diameter of the World Wide Web. , Nature 1999. M., Kumar, et al.. The web as a graph. Donato, D., Laura, L., Leonardi, S., and Millozzi, S. 2007. The Web as a graph: How far we are. ACM Trans. Internet Technol. 7, 1 (Feb. 2007), 4.	Jiang	Nov 15
    Page rank	Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry (1999). The PageRank citation ranking: Bringing order to the Web.

  • Lucene :
    • Use Lucene to build a search engine.
    • Lecture slides
    • A good Lucene tutorial site. There are also sample code.
    • Lucene in Action book.
    • A java program to index DBLP data (DBLP.java). Since dblp.xml file is rather large (~879MB), SAX XML parser rather than DOM parser is used.
    • DBPedia
• Project: a sample java program to construct a graph from SUMO2 (~30MB) ontology. The output is a txt file depicting the graph in graphviz format. The graph is then draw using graphvis. The fdp layout reault is here .

  The following table lists some ontologies and their corresponding graphs.

  Ontology	graph txt file	graph
  1. SUMO.owl (323KB)	sumoSubclass.txt(~700 edges)	subclass fdp layout
  2. All the relatestion extracted using jena. The java program	sumoAll.txt(~2700 edges)	sumoAll fdp layout, circle layout, twopi layout
  3. dbpedia.owl(~700KB)	graph txt
  4. SUMO2.owl(~30MB)	graphviz txt	twopi layout(79MB) , a 3D fig produced by Wang Hao
  5. SUMO2 subclass (5000 edges)	graphviz txt	fdp fig , dot fig , twopi fig ,
  6. SUMO2 subclass & domain range(7000 edges)	graphviz txt	fdp fig , dot fig , twopi fig ,
  7. SUMO2 domain range (1700 edges)	graphviz txt	fdp fig , dot fig , twopi fig ,
  8. SUMO2 classes	graphviz txt	fdp fig , dot fig , twopi fig ,

  Consider the following improvements from this example:

  • Other ontologies. In addition to DBPedia, you can find ontologies in
    • Other semantic web data examples .
    • Semantic web search engines: falcons, swoogle.
  • Other relations. This example only shows ObjeectProperty relation. Can you extract subclass relationship? How about dataProperty relationship?
  • More accurate relations. Currently the graph extraction is based on XML structure of the owl file. This will miss some relations if the syntax varies. Can you use Jena api to extract more accurate relations? What if a property misses a domain or range? graph--> remove multiple edges and self loops -->
  • Visualization. Graphviz is used in this example. The command to run graphviz is here.

    Pajek is a more comprehensive visualization tool for network analysis. Can you use Pajek to analyse the grnetwork in addition to visualization? Can you use Walrus to draw 3D visualization of human knowledge?

  • Build a search engine for the ontologies on labels, comments, and tags.
  • Degree analysis. Power law, histogram.
  • Pagerank analysis. While it is straightforward for strongly connected and aperiodic graph, you need to consider what if there are isolated components, dead ends. Consider the following when you summarise your project:
    • what is the maximal size of graph you can process?
    • what is the damping factor you chose? What if the damping factors are different?
    • When does the result converge? How many iterations are required in genral? Can you draw the converge trend using a diagram?
    When pagerank is done, you can consider what is the relationship between pagerank and degree rank. You can use Spearman corelation coefficinet to measure the relations.
  • Path length and diameter. Clustering coefficient. Small world. Floyd-Warshall is an algorithm to find the shortest paths in a weighted graph. You can use API (e.g., JUNG, a java API for network analysis) or an interactive tool (such as Pajek) to do some of the analysis.
  • Betweeness, closeness, ...
  • Please write a web page describing your project and related data. Add a a link to your web page in our 569_2011 page.