PageRank and rank-reversal dependence on the damping factor
S-W Son1, C Christensen, P Grassberger
1Complexity Science Group, University of Calgary, Calgary, Canada T2N 1N4. sonswoo@hanyang.ac.kr
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|February 2, 2013
Summary
The PageRank algorithm
Area of Science:
- Computer Science
- Network Analysis
- Information Retrieval
Background:
- PageRank (PR) is a fundamental algorithm for evaluating web page importance.
- The damping factor (d) is a critical parameter influencing PR calculations.
- Understanding rank stability is crucial for information retrieval and business success.
Purpose of the Study:
- To investigate the stability of PageRank scores.
- To analyze rank reversals as a function of the damping factor (d).
- To identify network structures contributing to rank instability.
Main Methods:
- Analysis of a World Wide Web network domain.
- Calculation of PageRank for varying damping factors (d).
- Application of Pearson, Spearman, and Kendall correlation measures to assess rank stability.
Main Results:
- Frequent rank reversals observed across a broad range of damping factors (d).
- PageRank vector correlation drops significantly as d deviates from 0.85.
- Rank reversals occur even in networks without rank sinks, linked to network bottlenecks.
Conclusions:
- PageRank stability is sensitive to the choice of the damping factor.
- Rank reversals are a common phenomenon in web networks.
- Relative rank stability is improved around d=0.65 compared to d=0.85 for the studied network.
Related Concept Videos
01:20Types of Damping
If the amount of damping in a system is gradually increased, the period and frequency start to become affected because damping opposes, and hence slows, the back and forth motion (the net force is smaller in both directions). If there is a very large amount of damping, the system does not even oscillate; instead, it slowly moves toward equilibrium. In brief, an overdamped system moves slowly towards equilibrium, whereas an underdamped system moves quickly to equilibrium but will oscillate about...
01:07Damped Oscillations
In the real world, oscillations seldom follow true simple harmonic motion. A system that continues its motion indefinitely without losing its amplitude is termed undamped. However, friction of some sort usually dampens the motion, so it fades away or needs more force to continue. For example, a guitar string stops oscillating a few seconds after being plucked. Similarly, one must continually push a swing to keep a child swinging on a playground.
Although friction and other non-conservative...
Although friction and other non-conservative...
01:18Second Order systems II
In an underdamped second-order system, where the damping ratio ζ is between 0 and 1, a unit-step input results in a transfer function that, when transformed using the inverse Laplace method, reveals the output response. The output exhibits a damped sinusoidal oscillation, and the difference between the input and output is termed the error signal. This error signal also demonstrates damped oscillatory behavior. Eventually, as the system reaches a steady state, the error diminishes to zero.
If ζ...
If ζ...
01:19Concept of Resonance and its Characteristics
If a driven oscillator needs to resonate at a specific frequency, then very light damping is required. An example of light damping includes playing piano strings and many other musical instruments. Conversely, to achieve small-amplitude oscillations as in a car's suspension system, heavy damping is required. Heavy damping reduces the amplitude, but the tradeoff is that the system responds at more frequencies. Speed bumps and gravel roads prove that even a car's suspension system is not immune...
01:17Design Example: Underdamped Parallel RLC Circuit
Consider designing an oscillator circuit, a crucial component in various electronic devices and systems. The objective is to create an oscillator circuit with specific characteristics: a damped natural frequency of 4 kHz and a damping factor of 4 radians per second. To accomplish this, a parallel RLC circuit is employed, known for its ability to sustain oscillations at a resonant frequency. In this case, the damping factor is pivotal in achieving the desired performance.
Starting with a fixed...
Starting with a fixed...
01:30Quantitative Aspects of Drug-Receptor Interaction
The receptor occupancy theory connects a drug's response to the number of occupied receptors. With higher drug concentrations, more receptors are occupied, leading to increased responses. The formation of drug-receptor complexes involves association and dissociation rates, which reach equilibrium when the forward and backward reactions are equal. The equilibrium association constant (Ka) and its inverse, the equilibrium dissociation constant (Kd), indicate drug affinity. Higher Ka and lower Kd...