Identify the nodes in the strongly connected core.

Identify the set of OUT nodes.

Outline why the edge between node 2 and node 1 is a tendril.

Identify two reasons why an edge may disappear in the new graph, for example the edge between node 5 and node 4.

State how many hyperlinks are in the document corresponding to node 6.

Power laws are often used to model phenomena occurring in very large networks and predict their evolution. Power laws may be suitably applied in different cases, in the context of the World Wide Web.

With reference to the relation between the number of documents in the web and the number of hyperlinks in each of them, suggest how power laws may help to explain the shape of the World Wide Web.

Award [1] for all three correct.
3, 5, 6

Award [1] for both correct.
4, 8

No;
Because 2 reaches the node 3 that is in the SCC;

Award [2 max]
There is no longer a link between 5 and 4;
because
5 has deleted its link / 5 no longer finds 4 interesting/relevant;
4 has changed its URL;
4 has removed itself from the internet;

4

Award marks as follows up to [5 max].
Award up to [1] for showing understanding of what a power law is, [2] for addressing both ideas of incremental web and preferential connectivity (award only [1] if one is addressed), and [2] for discussing them in context AND mentioning some element of the web graph.

(Incrementality of web): Number of nodes in the web increases (nodes are not deleted) / New nodes (documents) have hyperlinks that connect to existing nodes in the web;

(preferential connectivity): This connectivity happens following some preferential element/affinity/alikeness (e.g. common theme) and over time it induces an aggregation of nodes;

(Incrementality and preferential connectivity): Have the consequence that the SCC grows;

(Nodes are not deleted, but) some of the hyperlinks in documents may be changed/deleted/break over time, this may produce isolated nodes;

(Power law – proportionality): Relates two quantities, x and y, when y is proportional to x^c, for some constant c;

The probability for a new document N to be connected to some document M (with a certain out-degree) is proportional/depends on the probability that the hyperlinks in N to connect to M (i.e. the sum of the out-degrees of the nodes reached from N, recursively);

Therefore, a few nodes receive many in-links (because many nodes link to them directly or indirectly based on preference), whereas nodes that have a few in-links are probably new;

Niche themes/new themes with new language/obsolete themes (when theme is a preference) typically bypass the SCC, making tendrils and tubes;