PaperlayerView exact revision on arXiv

Source-linked AI summary

Unequal Opportunities in Multi-hop Referral Programs

Yiguang Zhang, Augustin Chaintreau

arXiv:2112.00269v1cs.SI

TL;DR

The paper examines whether multi-hop referral programs alleviate or amplify disparities already present in one-hop referrals, an important question given structural bias in social networks. Using four real-world networks and homophilic-model analysis, it finds that outcomes depend on referral strategies and network conditions, with a precise condition for bias change in the unconstrained case.

  • Problem

    Because structural network bias can disadvantage minority groups in one-hop referral programs, it is unclear when higher-hop referrals alleviate or amplify those disparities.

    Source: §1 · pp. 1–2

  • Method

    The paper studies four real-world networks and analyzes referral strategies in homophilic models with majority and minority groups, including active and passive gains.

    Source: §1 · p. 2

  • Results

    Multi-hop bias changes depend on network structure and referral strategy, and the analysis gives a threshold condition for when higher hops alleviate or amplify one-hop bias.

    Source: §1 · p. 2, §6 · p. 13

  • Takeaways & Limitations

    Multi-hop referrals may mitigate unfairness, but should be deployed after testing network conditions.

    Source: §1 · p. 3

    The analysis assumes that every successful referrer–referee pair yields the same gain.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

As modern social networks allow for faster and broader interactions with friends and acquaintances, online referral programs that promote sales through existing users are becoming increasingly popular. Because it is all too common that online networks reproduce historical structural bias, members of disadvantaged groups often benefit less from such referral opportunities. For instance, one-hop referral programs that distribute rewards only among pairs of friends or followers may offer less rewards and opportunities to minorities in networks where it was proved that their degrees is statistically smaller. Here, we examine the fairness of general referral programs, increasingly popular forms of marketing in which an existing referrer is encouraged to initiate the recruitment of new referred users over multiple hops. While this clearly expands opportunities for rewards, it remains unclear whether it helps addressing fairness concerns, or make them worse. We show, from studying 4 real-world networks and performing theoretical analysis on networks created with minority-majority affiliations and homophily, that the change of bias in multi-hop referral programs highly depends on the network structures and the referral strategies. Specifically, under three different constrained referral strategies which limit the number of referrals each person can share to a fixed number, we show that even with no explicit intention to discriminate and without access to sensitive attributes such as gender and race, certain referral strategies can still amplify the structural biases further when higher hops are allowed. Moreover, when there is no constraint on the number of referrals each person can distribute and when the effect of referral strategies is removed, we prove a precise condition under which the bias in 1-hop referral programs is amplified in higher-hop referral programs.

1 Introduction

The paper asks when multi-hop referrals change disparities already associated with one-hop opportunities, a gap that matters because network structure can disadvantage minority groups. Empirical study of four networks and analysis of homophilic models show that outcomes depend on referral strategy and network conditions.

1 Introduction

  • The paper examines higher-hop referral programs because their effects on disparities are less understood than those of one-hop programs.Prior work found that minority-group population bias is amplified when comparing users’ numbers of friends.Source: §1 · pp. 1–2
  • The study counts all referrers to each referee, defines gains by referral-forest distance, and limits programs to a fixed finite number of hops.The induced referrer–referee graph is termed the referral subgraph.Source: §1 · p. 2
  • Across four real-world networks and homophilic models, multi-hop referral bias can worsen or lessen 1-hop disparities depending on strategy and network structure.The direction also depends on whether active or passive gains are considered.Source: §1 · p. 2
  • With constrained strategies, 2-hop programs can change 1-hop bias without explicit discriminatory intent, while unconstrained programs amplify it under specified population and interaction conditions.The analysis gives a threshold for the direction of change; one alleviation case is an extreme population ratio with non-extreme homophily.Source: §1 · pp. 2–3
  • The authors conclude that multi-hop referrals may mitigate unfairness, but should be deployed after testing network conditions.They advocate network-aware referral choice to balance efficiency and fairness.Source: §1 · p. 3

2 Related Work

Related work studies network influence and virtual marketing, but pays less attention to how these strategies affect disparities across demographic groups. Prior structural-bias work focuses on direct influence, leaving higher-hop referral fairness unexamined.

2 Related Work

  • Virtual marketing research largely targets company benefits, while the effects of these strategies on demographic disparities are less studied.The cited areas include influence maximization and revenue maximization [6][7][8][2][9].Source: §2 · p. 3
  • Research has documented algorithmic bias in classification, word embeddings, ranking, and graph recommendations [11][12][13].The graph-recommendation work uses a homophilic network model.Source: §2 · p. 3
  • Structural-bias studies of social networks have focused on direct influence, although higher-hop neighbors can affect referral revenue.This paper presents itself as the first to study network bias through indirect influence.Source: §2 · p. 3

3 Empirical results

Across four real-world networks, the direction of bias change from one-hop to two-hop referrals varies with the referral strategy and whether active or passive gains are considered. The empirical results show that one-hop behavior alone does not reliably predict multi-hop fairness.

3.1.1 Deezer [17]–3.1.4 Twitch [19]

  • The four empirical networks are Deezer, DBLP, Instagram, and Twitch, with users grouped by gender or, for Twitch, language.Instagram users’ genders were inferred from names, and the analysis used Twitch’s English- and German-labelled subgraph.Source: §3.1.1 · p. 4, §3.1.2 · p. 4, §3.1.3 · p. 4

3.2 Referral strategies

  • The study compares first- and second-hop gains across referral strategies, including constrained strategies limited to one referral per person and an unconstrained linear strategy.The simulations were repeated 100 times on each network, and average active- and passive-gain ratios were reported separately.Source: §3.2 · p. 5, §3.3 · p. 6

3.3 How does bias change from 1-hop to 2-hop?

  • The empirical homophily measure compares the observed cross-group edge fraction with its expected fraction, 2r(1 − r), under no homophily.Here, r is the minority population ratio; cross-group edges connect nodes from different groups.Source: §3.3 · pp. 5–6

3.3.1 Active gain

  • Acceptance-driven referrals alleviate one-hop active-gain bias in all four networks, while linear referrals alleviate it in Deezer and DBLP but amplify it in Instagram and Twitch.The Table 1 caption reports these comparisons; the accompanying prose gives the opposite direction for the linear-strategy dataset comparisons.Source: Table 1 · p. 6

3.3.2 Passive gain

  • For passive gains, two-hop referrals alleviate one-hop bias under random and acceptance-driven strategies in all four datasets; under the linear strategy, passive-gain ratios match active-gain ratios.The supplied passage also reports that popularity-driven referrals amplify bias in Deezer, Instagram, and Twitch, but its account of the remaining dataset is truncated.Source: §3.3.2 · p. 6

DBLP.

  • Across strategies and datasets, multi-hop bias change is not reliably inferred from the corresponding one-hop referral result.The paper notes that the direction of bias change can vary with strategy and with whether active or passive gains are examined.Source: DBLP · pp. 6–7

4 Theoretical analysis for active gains

The theoretical analysis models referrals on a minority–majority network with homophily and compares how referral strategies change active-gain bias across hops. Under the linear strategy, whether higher hops reduce bias depends on network conditions, with a precise threshold and a distinct high-homophily limit.

4.1 Model and definitions

  • The BPA model represents a minority group with population ratio r and uses ρ for the tendency to accept cross-group connections, incorporating preferential attachment and homophily.The model initializes with one red and one blue node; new nodes are red with probability r and blue with probability 1 − r.Source: §4.1 · pp. 7–8

4.2 The 1-hop ratio is no greater than the minority ratio

  • In the 1-hop limit, red nodes’ expected active-gain share equals their population share under random and popularity-driven strategies, but is lower under acceptance-driven and linear strategies.The equality holds when gain is independent of degree and equal across groups, as in the random and popularity-driven strategies.Source: §4.2 · p. 8

4.3 Constrained referral strategies

  • For constrained strategies, random and popularity-driven referrals give red and blue nodes equal 2-hop success chances, while acceptance-driven referrals cannot amplify the 1-hop active-gain bias.Under acceptance-driven referral, the red share of expected active gain in the second hop is no greater than in the first.Source: §4.3 · pp. 8–9

4.4 Linear referral strategy: a precise threshold

  • The linear-strategy theorems for 2-hop active gains also hold for k hops, with the k-hop ratio tied to red and blue nodes’ blue-neighbor counts.For any k > 2, the ratio is essentially the number of blue neighbors of red nodes divided by that of blue nodes.Source: §4.4 · p. 9
  • In the unconstrained linear program, 2-hop active gains reduce 1-hop bias when the minority ratio is small and cross-group acceptance is high; the reduction has a precise threshold.The threshold depends on the population ratio and homophily, and cannot be written directly in r and ρ because it requires solving for a cubic root.Source: §4.4 · p. 10
  • As homophily becomes extreme, the 1-hop red gain ratio approaches r, while the 2-hop ratio approaches zero.The analysis attributes the 2-hop limit to red nodes having few blue direct neighbors, through whom they extend their 2-hop neighborhoods.Source: §4.4 · pp. 10–11

5 Insights on passive gains

The passive-gain analysis finds that the direction of bias change depends on referral strategy and gain type. Under constrained strategies, referral selection and network effects provide different explanations for changes across hops; under the linear strategy, the active-gain conditions also apply to passive gains.

Linear referral strategy

  • Under the linear strategy, the conditions for alleviating 1-hop bias in 2-hop active gains also hold for passive gains.The expected-sum ratios of k-hop passive gains are equivalent to those of k-hop degrees.Source: §5 · p. 11

Constrained referral strategies

  • Under random referrals, 2-hop passive-gain bias is alleviated; under popularity-driven and acceptance-driven referrals, it is amplified.The direction across constrained strategies differs from the linear program, where the change depends on minority ratio and homophily.Source: Figure 2 · p. 11, §5 · p. 11
  • Color-blind random selection alleviates first-hop passive-gain bias because the first-hop selection reduces homophily’s effect on the next selection.Across the constrained strategies, first- and second-hop red passive-gain ratios converge to the minority ratio as ρ approaches 0 or 1.Source: §5 · pp. 11–12
  • Popularity-driven referrals amplify passive-gain bias as intermediate referrers are more likely to reach popular, mostly blue nodes.The text attributes this to intermediate referrers’ high degree, including their selection as the highest-degree neighbor of the initial referrer.Source: §5 · p. 12
  • Acceptance-driven referrals involve competing effects: red nodes’ lower first-hop acceptance creates more second-hop opportunities, while blue intermediates are more likely to succeed onward.The text says the first effect can release the 1-hop bias when it outweighs the second.Source: §5 · p. 12

6 Conclusion

The paper concludes that higher-hop referrals can either amplify bias or contribute to fairness, depending on referral strategy and whether active or passive gains are considered. Its theoretical results distinguish constrained strategies from the linear strategy, for which the bias change has a necessary and sufficient condition.

6 Conclusion

  • Empirical results and theory indicate that higher-hop referrals can amplify bias or contribute to fairness, depending on strategy and gain type.For constrained strategies, networks with varying inherent bias and homophily agree in the direction of bias change.Source: §6 · p. 13
  • For the linear strategy, the agreement across network conditions does not hold, and the paper proves a necessary and sufficient condition for bias alleviation at higher hops.The conclusion describes this analysis as removing strategic effects and examining the network’s structural bias directly.Source: §6 · p. 13
  • Because prior algorithm-bias analysis primarily focuses on 1-hop neighbors, the paper argues that 1-hop behavior alone cannot establish long-run impact.The conclusion presents this as an initial examination of bias in higher-hop neighbors.Source: §6 · p. 13

B Proof of Theorem 4.1

The proof treats the BPA network with r < 0.5 and derives the needed degree-count results through recursions over four possible node-connection cases. It uses a limiting equation for α* and an asymptotic sequence lemma.

B Proof of Theorem 4.1

  • Theorem 4.1 is considered for BPA networks with r < 0.5 and k > 1.The supplied theorem statement is partial and does not include its conclusion.Source: B Proof of Theorem 4.1 · p. 14
  • The proof forms degree-count recursions by considering four cases for the colors of each new node and its connection target.The four cases are red-to-red, red-to-blue, blue-to-blue, and blue-to-red connections.Source: B Proof of Theorem 4.1 · p. 15
  • The limiting minority proportion α* satisfies an equation, and the proof invokes an asymptotic sequence lemma to handle the recursions.The proof also takes expectations and uses lemmas to obtain the stated bounds, though their full expressions are not present here.Source: B Proof of Theorem 4.1 · pp. 16–17

C Proof of Corollary 4.2

For BPA networks with r < 0.5, Corollary 4.2 bounds the asymptotic red share of expected k-hop degree under the linear referral strategy by the minority population share. The proof reduces the comparison to an inequality involving α* and ρ.

C Proof of Corollary 4.2

  • Under the linear referral strategy, the asymptotic red share of expected k-hop degrees is no greater than the minority population ratio r.The result applies to BPA networks with r < 0.5 as t tends to infinity.Source: C Proof of Corollary 4.2 · p. 18
  • The comparison is expressed as an inequality involving ρ and the limiting proportion α*.The supplied condition states that ρ/[1−(1−α*)(1−ρ)] ≤ 1/[1−α*(1−ρ)].Source: C Proof of Corollary 4.2 · p. 18
  • The proof says this inequality follows from the definition of α* and ρ..Source: C Proof of Corollary 4.2 · p. 18

D Proof of Corollary 4.4

Corollary 4.4 considers BPA networks with r < 0.5 in the limit as ρ approaches zero. The supplied proof passages give the equation for α* and a limiting value for a displayed quantity.

D Proof of Corollary 4.4

E.1 Proof of Lemma B.2

The proof establishes its lemma by induction, writing recursive expressions for blue-node degree counts across the four growth cases. It uses limiting β parameters and a cited inequality to compare their differences.

E.1 Proof of Lemma B.2

  • The proof proceeds by induction, deriving recursive expressions for M(k) from the four possible node-connection cases.The displayed case descriptions track contributions to the blue-node degree counts.Source: §E.1 · pp. 19–20
  • The proof defines limiting β parameters using α* and ρ, then applies the resulting relations to the recursions.It defines g(x,y) and h(x,y) as intermediate expressions.Source: §E.1 · p. 21
  • An inequality attributed to Theorem 4.6 in yields β1−β2 < β3−β4 as t tends to infinity.The proof uses this comparison to show a quantity is smaller than 1.Source: §E.1 · p. 21

E.2 Proof of Lemma B.1

The proof states bounds for quantities indexed by i and concludes with an exponent choice within the interval (-1/3, 0). The supplied lemma statement applies to either color and indices i from 1 to 4.

E.2 Proof of Lemma B.1

  • The lemma is stated for either color, i in {1, 2, 3, 4}, and any k.The supplied statement does not include the result asserted for those choices.Source: §E.2 · p. 21
  • C*,**(t) is upper bounded by t^3, while beta_i(t) and beta_i are bounded by C2 for every i and t.The passage states that positive constants C1 and C2 exist, but omits the expression associated with C1.Source: §E.2 · p. 21
  • The proof uses -1/4 as an exponent within the interval (-1/3, 0).The passage calls this choice arbitrary and says the proof is finished.Source: §E.2 · p. 22

E.3 Proof of Lemma B.3

The proof derives asymptotic behavior in regimes defined by how c1 compares with c3. It uses the recurrence for at, the assumption on dt, and the expression for bt.

E.3 Proof of Lemma B.3

  • For c1 < c3, the displayed asymptotic expression includes (log t)^m and t^(c3−c1), with a (1+o(1)) factor.The extracted coefficient in the passage is not sufficiently clear to restate safely.Source: §E.3 · pp. 22–23
  • The proof proceeds from the recurrence for at, assuming dt = 1 + o(t^−ε) for some ε > 0, and combines this with the stated form of bt.The passage gives bt = (log t)^m t^(c3−1)(1 + o(1)).Source: §E.3 · pp. 22–23
  • The derived asymptotic behavior has separate regimes for c1 > c3, c1 = c3, and c1 < c3.The passage gives O(1) when c1 > c3 and O((log t)^(m+1)) when c1 = c3.Source: §E.3 · p. 23
Loading 2112.00269v1…