A web graph is the set of all nodes corresponding to web pages, plus the directed edges, the hyperlinks, that connect them. It matters because search engines read the web through this structure: which pages link where, and with what words, is how a crawler finds a page and part of how a search engine judges it.
Two meanings of the term
In search and information retrieval, the web graph is the link structure of the web described above. In mathematics the same name means something else: a web graph is a stacked prism graph with the edges of the outer cycle removed, and some authors use the term for the stacked prism graph itself. This page is about the first meaning.
How it works
Every page is a node and every hyperlink is a directed edge. In-links are the links into a page, and out-links are the links out of it. The text of the link carries meaning too. The text around the origin of a hyperlink, inside the a tag, is called anchor text.
In-links are spread very unevenly. Across a range of studies, the number of in-links to a page has averaged roughly 8 to 15, and the distribution follows a power law, with an exponent typically reported as 2.1. In plain terms, a few pages collect a huge share of links and most pages get very few.
The bowtie shape
The web graph is not strongly connected, so you cannot reach every page from every other page. Several studies describe it as a bowtie, with three main groups of pages called IN, OUT and SCC.
SCC is the knot in the middle. From any page in SCC you can reach any other page in SCC. IN feeds into it: from any page in IN you can reach any page in SCC by following links. OUT hangs off the other side: from SCC you can reach any page in OUT. The traffic only goes one way. You cannot get from SCC back to IN, or from OUT back to SCC.
In several studies IN and OUT are roughly equal in size, and SCC is somewhat larger. The rest forms smaller shapes. Tubes are small sets of pages outside SCC that lead straight from IN to OUT, and tendrils either lead nowhere from IN, or from nowhere to OUT.
An example
A new product site launches with a home page and a few blog posts that link to each other, and nothing on the web links to them. In bowtie terms the site sits in IN: its own links lead out into the web, but nothing in the connected core links back to it. A crawler following links from the core never arrives. Once a directory listing, a forum reply or a partner page links to it, there is a path in, and the site starts to look like part of the connected web.
How to check where your site sits
You cannot see the whole graph, but you can see your corner of it. Count the pages that link to yours, the in-links, and read the anchor text they use. Then check your own pages link to each other, so a crawler that lands on one page can reach the rest. A page with no internal links pointing to it is an orphan, even on your own site.
Studying web graphs
Researchers work with web graphs too large to hold in memory as they are. WebGraph is a framework for graph compression aimed at studying web graphs. It can read a compressed graph without decompressing it, delaying decompression until it is needed, and its HyperBall algorithm was used to show that Facebook has just four degrees of separation. It is implemented in Java and Rust.
Common mistakes
Treating links as a count only. Anchor text tells search engines what the linked page is about, so "click here" wastes the link. The other is ignoring direction: a link you give out does not put you on the path in. Only links pointing to you do.
Frequently asked questions
What is a web graph in simple terms?
A map of web pages, where each page is a point and each link is an arrow from one page to another.
What is the bowtie structure of the web?
The finding that the web splits into a connected core (SCC), pages that lead into it (IN) and pages it leads out to (OUT), with one-way paths between the groups: links lead from IN to SCC to OUT, never back.
What is the difference between in-links and out-links?
In-links point into a page; out-links point out of it. For being found, in-links are the ones that count.