Examples: Wikipedia, the Web, biological networks (brains), communication networks (email, Internet), transportation networks (air flights), social media (Twitter).
Links are directed and often weighted (intensity of interaction, similarity, traffic flow).
Features of Directed and Weighted Networks:
Web Network:
Huge information network with pages connected by hyperlinks.
Browsers navigate links using HTTP, content presented in HTML.
Web Structure:
Nodes represent pages or websites.
Heavy-tailed distribution of in-degree, ultra-short paths, popular hub pages.
Large strongly connected component.
Text Similarity:
Represent documents as high-dimensional word vectors.
Cosine similarity to measure text similarity among pages.
Web has clustered structure with semantically related pages.
PageRank:
Node centrality measure based on a random walk model.
Measures the prestige of Web pages.
Important for ranking search engine results.
Information Diffusion Networks:
Track spread of content on social media (retweets, links, images, hashtags).
Identify viral concepts and influential accounts.
Node out-strength and in-strength to characterize information producers and consumers.
Weighted Networks from Bipartite Graphs:
Links weighted by co-occurrence relations (co-citations, product recommendations, word/tag similarity).
Weighted Network Pruning:
Dense networks may need pruning by filtering low-weight links.
Heavy-tailed weight distributions require local weight thresholds.
Extract backbone of the network by identifying statistically significant links.
Motivation
Weighted networks capture the intensity of connections, providing more detailed insights into interactions, influence, and network dynamics than unweighted networks.
A weight encodes intensity, capacity, or distance.
Examples of weighted networks
Unweighted graphs treat every edge as identical. Real connections are not.
Traffic volume between airports
Citation counts between papers
Synaptic strength between neurons
Trade flow between countries
Co-authorship frequency
Two flavors of weight
Before computing anything, ask what a large weight means.
Squaring rewards concentration: a few large shares dominate the sum.
Node
Weights
Shares \(p_{ij}\)
\(Y_i\)
\(1/Y_i\)
even
4, 3, 3
.4, .3, .3
0.34
2.9
skewed
8, 1, 1
.8, .1, .1
0.66
1.5
Read \(1/Y_i\) as the effective number of edges: how many neighbors the node behaves as if it had, if those ties were equal. Both nodes have three neighbors, but the skewed node leans on ~1.5 of them; the rest are almost dead weight.
Limiting cases: all edges equal gives \(p_{ij} = 1/k_i\), so \(Y_i = 1/k_i\) and \(1/Y_i = k_i\) (you “use” every edge). One edge dominating drives \(Y_i \to 1\) and \(1/Y_i \to 1\) (effectively a single tie).
Example:
Traffic Networks:
Capture various kinds of traffic.
Examples:
Air/Transportation Networks: Weights represent passengers or flights between airports, cars between intersections.
Internet: Weights denote packets or bits of data between routers.
Wikipedia: Weights represent clicks between articles.
Focus Example:
Web traffic network: Similar to Wikipedia but includes all websites. ## Monitoring Web traffic
Methods:
Browsers, toolbars, or extensions record click data and transmit it to a server.
ISPs monitor packets carrying HTTP/HTTPS requests, including target host/page and source URL (referer).
Bias in Data Collection:
Browser-based method: Only captures traffic from users with traffic-monitoring software.
ISP-based method: Only captures packets passing through ISP routers.
Advantages:
Both methods enable large collections of Web traffic data.
Data Analysis:
Can count clicks between individual pages.
Consider aggregate traffic at the level of entire websites identified by hostnames. ## Node strength distribution
Cumulative distributions of node in-strength (website traffic) and link weight in a Web traffic network.
Almost one billion clicks, representing the combined Web browsing activities of about 100,000 anonymous users
Collected by Indiana University between 2006 and 2007.
The resulting network has about 4 million sites and 11 million weighted directed links
## Example: Web Traffic
Link Filtering and Network Backbones
What is a backbone?
A backbone is a sparse subgraph that keeps the important edges and drops the rest. Same nodes, far fewer edges: the skeleton that carries the network’s structure.
Why: real weighted networks are dense and noisy. Most edges are weak or redundant and hide what matters.
Two ways to define “important”:
Global rule: one network-wide criterion (weight threshold, maximum spanning tree, high betweenness). Blind to local context, so a node whose ties are all weak loses every edge.
Local rule: judge each edge against its own node’s weights. The disparity filter keeps edges heavier than a node would spread at random, preserving significant ties at every scale.
A backbone is a modeling choice. The criterion encodes what you think matters, so one network has different backbones under different rules.
Link Width: Represents the number of shared compounds.
Visualizations:
Full network shown in the inset.
Main image shows the backbone network with significant links (w = 0.04).
Source: Adapted from Ahn et al. (2011) under CC BY 4.0 license.
The density problem
Dense weighted networks are often slow to analyze. We want the essential edges.
Naive global threshold: drop every edge below some \(w^{*}\).
The flaw: a node whose ties are all weak loses every edge, even when those ties are locally its most important. A global cutoff erases locally significant weak ties.
Additional Motivation for link Filtering
Challenges with Dense Networks:
Difficult to visualize and study (“hairballs”).
Contain many unimportant links
Many links may not be significant.
Need for Pruning:
Prune low-weight links in weighted networks.
Essential for co-occurrence networks to remove noise.
Example:
Network of documents or Web pages linked by text similarity (shared keywords).
Unrelated documents may share a few generic keywords, creating insignificant links.
Goal:
Filter out low-weight links to obtain a sparser, more meaningful network.
Code
## When to prune-**Keep full $W$:** strength, exact paths, flow conservation-**Extract backbone:** visualization, community detection on dense graphs, denoisingPruning is a modeling choice, not a default. Know what each edge represents before deleting it.
When to prune
Keep full \(W\): strength, exact paths, flow conservation
Extract backbone: visualization, community detection on dense graphs, denoising
Pruning is a modeling choice, not a default. Know what each edge represents before deleting it.
Pruning Method-1: Threshold
Simplest Pruning Approach:
Remove all links below a certain weight threshold.
Effective in many settings.
Challenges with Global Threshold:
Ineffective for networks with heavy-tailed distribution of link weights.
Common in co-occurrence, traffic, and other weighted networks.
Issues with Heterogeneous Weights:
Hard to find a suitable threshold.
Risk of preserving insignificant links.
Risk of disconnecting low-strength nodes by removing significant low-weight links.
Significance of links varies depending on node strength.
Pruning Method-2: Disparity filter
Serrano et al.: judge each edge against its own node’s weight distribution.
Normalized weight \(p_{ij} = w_{ij}/s_i\). Null model places \(k\) weights uniformly at random.
\[\alpha_{ij} = (1 - p_{ij})^{\,k_i - 1}\]
Keep the edge if \(\alpha_{ij} < \alpha\) (heavier than the random baseline). This preserves significant ties at every scale, hub and periphery alike.
Additioanl Examples of weighted networks
Information diffusion network overview
Diffusion network’a are classic examples of a weighted network
Nodes represent people; links represent pieces of information (memes).
Memes include images, movies, Web links, phrases, hashtags.
Tweets can carry multiple memes (e.g., hashtags and links in one message).
Each meme identified by a text string (URL) or hashtag.
Hashtags prefixed by the hash mark (#) express concepts or topics.
Diffusion network definition
Meme Propagation:
Same meme can create multiple cascade trees (stars).
Example: multiple users sharing the same link or hashtag.
Aggregation:
Aggregating star trees forms a forest, called the diffusion network.
Building a Diffusion Network:
Identify the meme(s) to analyze.
Example interests: single hashtag (#elections, #soccer), all links to specific news sources.
Source: Image from Shao et al. (2018b) under CC BY 4.0 license.
Recall: Star networks
Central node connected directly to multiple peripheral nodes.
All peripheral nodes have a direct link only to the central node.
No direct links between peripheral nodes.
Common in diffusion networks where a single source spreads information to many recipients.
Example: retweet cascade where many users retweet a meme from one original tweet.
Forms a “star” shape with the originator at the center and followers as the spokes.
Recall: Tree networks
Hierarchical structure with nodes and edges.
One root node (origin) with no parent.
Each node (except the root) has one parent node.
Nodes may have zero or more child nodes.
Example: Retweet cascades tree’s vs start networks
b follows a and also retweets a message from a (a=root node).
c follows a, but does not retweet a.
User may retweet messages retweeted by someone they follow.
h does not follow a, but retweets a’s message retweeted by g, who is followed by h.
Tracing these retweet chains, in theory we can reconstruct retweet cascade tree with
Twitter does not provide data about retweet cascades \(\rightarrow\)cascade tree becomes a star network
The same meme can generate many cascade trees (stars).
Multiple users can share the same link to a news article, or tweet using the same hashtag.
All star trees for a given meme create a forest (set of trees) that we call the diffusion network. In building a diffusion network, one must first formulate the meme, or memes, whose spread we want to analyze. We might be interested in a single hashtag, say #elections or #soccer; or in all links to articles from a news source or a set of news sources. For instance, when investigating online misinformation, we may wish to track stories from low-credibility sources that routinely spread fabricated news, hoaxes, conspiracy theories, hyper-partisan content, click bait, or junk science. *
Co-occurrence Networks
Arise from relationships between different types of entities.
Example: Citation networks
Directed Network:
Each link has a source and a target node.
Source nodes and target nodes can be separated, with duplicates if necessary.
Citation Network Example:
Source: Citing paper.
Target: Cited paper.
Constructing New Networks:
Co-citation Network:
Two papers are co-cited if both are cited by the same paper.
Link weight: number of papers citing both.
Co-reference Network:
Two papers are co-referenced if both cite the same paper.
Link weight: number of papers cited by both.
Characteristics:
Co-citation and co-reference networks are undirected, weighted networks.
Useful for finding related sets of publications.
Recall: Bi-Partite networks
Consists of two distinct sets of nodes.
Links only exist between nodes from different sets, not within the same set.
Often visualized by placing each set of nodes on opposite sides.
B=nx.complete_bipartite_graph(4,5)
Common example: collaboration networks (e.g., authors and papers).
Useful for modeling relationships between two different types of entities.
Example: Bipartite network
A bipartite network induced by “like” relationships.
Overview
Co-occurrence Network:
Created by projecting bipartite networks.
Represents two entities of the same type occurring together.
Links:
Connect nodes that share a common association.
Can be weighted by the frequency of co-occurrence.
Common Examples:
Students in the same classes.
Products purchased by the same customers.
Pages co-liked by Facebook users.
Applications:
Used in recommendations.
Targeted advertising.
Social Media Context:
User interactions (likes, shares) create links.
Aggregated data forms large co-occurrence networks.
Example: co-occurrence network
A user co-occurrence network derived from projecting the “like” network onto user nodes.