Understanding Graph Structures and Connectivity

A web crawler turns a collection of live web pages into a structure that can be studied. It visits pages, records their content, and notes which pages link to which other pages. In the resulting graph, each page is represented as a node and each hyperlink is represented as a relationship between two nodes. The crawler is therefore the foundation for later analysis: without collected page and link data, there is no network on which to calculate connectivity or importance.

spider.py begins with a starting URL and a requested crawl size. It fetches the starting page, extracts the links found on that page, and writes information to the SQLite database file spider.sqlite. The page is stored with a unique ID, its URL, and a count of outgoing links. The relationships created by those links are stored separately using the source page ID and target page ID.

The crawler does not finish after storing the starting page. Each page can reveal more URLs, so the crawler adds those links to the collection of possible future targets. It then chooses an unvisited link and repeats the fetch, extraction, and storage process. On a restart, spider.py begins from a random unvisited link in its queue. This lets successive runs explore different branches instead of repeatedly following only the first path discovered.

The important idea is that discovery and visitation are different states. A link can be known because it was extracted from a page, while its target page can still be unvisited. The queue connects these two stages: it holds discovered targets that can become future pages in the stored graph.

The database is persistent, so the collected pages and links remain on disk between program runs. When spider.py is run again, it checks the existing database and skips pages that have already been recorded. If one session collects 10 pages and a later session is asked to collect 20 pages, the later session fetches only the 10 new pages needed to extend the collection rather than re-fetching the original 10.

A single spider.sqlite database can contain pages discovered from more than one starting URL. For example, one session can begin at http://www.dr-chuck.com/ and another can begin at http://www.wikipedia.org/. These starting points are treated as separate webs, meaning they may form regions that are not directly connected to each other. Nevertheless, the crawler stores them in the same database and treats all unvisited links across the webs as one unified queue.

The database can therefore contain both connected clusters and loosely connected or isolated pages. The crawler does not maintain a separate visitation process for each starting point. When choosing the next page, it randomly selects from all unvisited links across the webs, so visits from different starting points can be interleaved.

The stored database is more than a list of URLs. Its page and link records support questions about the network: which pages link to a particular page, which pages a given page links to, and what statistics describe the network. The collected graph can be analyzed with algorithms such as a simplified page rank calculation. D3 can read the page and link data and render nodes and edges as an interactive graph, making clusters, highly connected hub pages, and isolated pages easier to see.