<jupyter_start><jupyter_text>Second Counterexample (Top Violation)<jupyter_code># Score and rank monotonicity counterexample in which the more important node loses score
# Node names correspond to the labeling in the paper

A_pre  = matrix(7, 7, [
    0, 0, 1/(k+1), 1/(k+1), 0, 0, 0,        #0: 0->2, 0->3
    0, 0, 1/(k+1), 0, 0, 0, 1/(k+1),        #1: 1->2, 1->6
    1/(k+3), 1/(k+3), 0, 0, 1/(k+3), 0, 1/(k+3), #2: 2->0, 2->1, 2->4, 2->6
    k, 0, 0, 0, 0, 0, 0,                    #3 k: 3->0
    0, 0, 1/(k+1), 0, 0, 1/(k+1), 0,        #4: 4->2, 4->5
    0, 0, 0, 0, k, 0, 0,            #5: k: 5->4
    0, k/(k+1), k/(k+1), 0, 0, 0, (k-1)/(k+1) #6 k: 6->1, k:6->2, k-1:6->6
])


A_post  = matrix(7, 7, [
    0, 1/(k+2), 1/(k+2), 1/(k+2), 0, 0, 0,        #0: 0->1, 0->2, 0->3
    1/(k+2), 0, 1/(k+2), 0, 0, 0, 1/(k+2),        #1: 1->0, 1->2, 1->6
    1/(k+3), 1/(k+3), 0, 0, 1/(k+3), 0, 1/(k+3), #2: 2->0, 2->1, 2->4, 2->6
    k, 0, 0, 0, 0, 0, 0,            #3 k: 3->0
    0, 0, 1/(k+1), 0, 0, 1/(k+1), 0,        #4: 4->2, 4->5
    0, 0, 0, 0, k, 0, 0,            #5: k: 5->4
    0, k/(k+1), k/(k+1), 0, 0, 0, (k-1)/(k+1) #6 k: 6->1, k:6->2, k-1:6->6
])


# Determinants are positive

det_pre = det(identity_matrix(7) - a * A_pre)
det_post = det(identity_matrix(7) - a * A_post)

lower_bound(solve(det_pre(a=2/3)(k=x)>0, x))
lower_bound(solve(det_post(a=2/3)(k=x)>0, x))

# Column sums of the adjugate (AKA PageRank multiplied by the graph size, by the determinant, and divided by 1 - a)

r_pre = vector([1]*7) * ~(identity_matrix(7) - a * A_pre) * det_pre
r_post = vector([1]*7) * ~(identity_matrix(7) - a * A_post) * det_post

assert r_pre[0] + r_pre[1] + r_pre[2] + r_pre[3]*k + r_pre[4] + r_pre[5]*k + r_pre[6]*k == (4 + k + k + k) * det_pre / (1 - a)
assert r_post[0] + r_post[1] + r_post[2] + r_post[3]*k + r_post[4] + r_post[5]*k + r_post[6]*k == (4 + k + k + k) * det_post / (1 - a)<jupyter_output><empty_output><jupyter_text>Score Comparison Node 0 is more important than node 1 when $\alpha=\frac23$.<jupyter_code>p = S(r_pre[0] - r_pre[1])

print("Node 0 is more important than node 1 when ⍺ = 2/3 for k", lower_bound(solve(p(a=2/3)(k=x)>0, x)))<jupyter_output>Node 0 is more important than node 1 when ⍺ = 2/3 for k ≥ 1<jupyter_text>It is also more important when $\frac23-\frac{2\sqrt k}{3\sqrt k+10}<\alpha\leq \frac23 + \frac k{3k+1}$.<jupyter_code>St = sturm(p)

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, l, r, power=2), l, r)
print()
printLimits(l(x=k), r(x=k))<jupyter_output>Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 14

-2*k/(3*k + 10) + 2/3 → 0 for k → ∞
k^2/(3*k^2 + 1) + 2/3 → 1 for k → ∞<jupyter_text>Score Counterexample Node 0 loses score when $\alpha = \frac23$.<jupyter_code>p = (1 - a) * r_post[0] / det_post - (1 - a) * r_pre[0] / det_pre

print("Node 0 loses score when ⍺ = 2/3 for k", lower_bound(solve(p(a=2/3)(k=x)<0,x)))<jupyter_output>Node 0 loses score when ⍺ = 2/3 for k ≥ 5<jupyter_text>It loses score also when $\frac23-\frac{2\sqrt k}{3\sqrt k+10}<\alpha\leq \frac23 + \frac k{3k+1}$.<jupyter_code>St = sturm(S(p.numerator()))

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, l, r, power=2), l, r)
print()
printLimits(l(x=k), r(x=k))<jupyter_output>Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 20

-2*k/(3*k + 10) + 2/3 → 0 for k → ∞
k^2/(3*k^2 + 1) + 2/3 → 1 for k → ∞<jupyter_text>Rank Counterexample  PRE Node 0 and 4 have the same importance.<jupyter_code>r_pre[0] - r_pre[4]<jupyter_output><empty_output><jupyter_text>POST Node 0 becomes less important than node 4 when $\alpha = \frac23$.<jupyter_code>p = S(r_post[0] - r_post[4])

print("Node 0 is less important than node 4 when ⍺ = 2/3 for k", lower_bound(solve(p(a=2/3)(k=x)<0,x)))<jupyter_output>Node 0 is less important than node 4 when ⍺ = 2/3 for k ≥ 5<jupyter_text>It is also less important when $\frac23-\frac{2\sqrt k}{3\sqrt k+10}<\alpha\leq \frac23 + \frac k{3k+1}$.<jupyter_code>St = sturm(p)

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, l, r, power=2), l, r)
print()
printLimits(l(x=k), r(x=k))<jupyter_output>Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 14

-2*k/(3*k + 10) + 2/3 → 0 for k → ∞
k^2/(3*k^2 + 1) + 2/3 → 1 for k → ∞<jupyter_text>Statements Outside Interval of Validity  Score Comparison<jupyter_code>p = S(r_pre[0] - r_pre[1])

St = sturm(p)

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, 0, l, power=2), 0, l)
printChanges(changes(St, r, 1, power=2), r, 1)
print("p(1) =", p(a=1))<jupyter_output>Number of zeros for 0 < ⍺ ≤ -2*x/(3*x + 10) + 2/3: 1 for k ≥ 14
Number of zeros for x^2/(3*x^2 + 1) + 2/3 < ⍺ ≤ 1: 1 for k ≥ 5
p(1) = 0<jupyter_text>Score Counterexample<jupyter_code>p = (1 - a) * r_post[0] / det_post - (1 - a) * r_pre[0] / det_pre

St = sturm(S(p.numerator()))

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, 0, l, power=2), 0, l)
printChanges(changes(St, r, 1, power=2), r, 1)
print("p(1) =", p(a=1))<jupyter_output>Number of zeros for 0 < ⍺ ≤ -2*x/(3*x + 10) + 2/3: 1 for k ≥ 14
Number of zeros for x^2/(3*x^2 + 1) + 2/3 < ⍺ ≤ 1: 1 for k ≥ 20
p(1) = (3*k^2 + 16*k + 16)/(k^3 + 13*k^2 + 50*k + 48)<jupyter_text>Rank Counterexample  POST<jupyter_code>p = S(r_post[0] - r_post[4])

St = sturm(p)

# Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

printChanges(changes(St, 0, l, power=2), 0, l)
printChanges(changes(St, r, 1, power=2), r, 1)
print("p(1) =", p(a=1))<jupyter_output>Number of zeros for 0 < ⍺ ≤ -2*x/(3*x + 10) + 2/3: 2 for k ≥ 14
Number of zeros for x^2/(3*x^2 + 1) + 2/3 < ⍺ ≤ 1: 1 for k ≥ 8
p(1) = (6*k + 8)/(k^4 + 6*k^3 + 13*k^2 + 12*k + 4)<jupyter_text>Demotion There are no nodes more important than node 0 (node 4 is a tie) before adding the edge when $\alpha=\frac23$.<jupyter_code>for i in range(7):
    if i == 0:
        continue
    p = S(r_pre[i] - r_pre[0])
    if p == 0:
        print("Node", i, "has the same score of node 0")
    else:
        try:
            kmin = lower_bound(solve(p(a=2/3)(k=x)>0,x))
            print("Node", i, "is ultimately more important than node 0 for k", kmin)
        except:
            print("Node", i, "is ultimately not more important than node 0")<jupyter_output>Node 1 is ultimately not more important than node 0
Node 2 is ultimately not more important than node 0
Node 3 is ultimately not more important than node 0
Node 4 has the same score of node 0
Node 5 is ultimately not more important than node 0
Node 6 is ultimately not more important than node 0<jupyter_text>There are no nodes more important than node 0 (and node 4 is a tie) also when $\frac23-\frac{2k}{3k+1}<\alpha\leq \frac23 + \frac k{3k+1}$.<jupyter_code>l, r = 2/3 - 2*k/(3*k+1), 2/3 + k/(3*k+1)

for i in range(7):
    if i == 0:
        continue
    p = S(r_pre[i] - r_pre[0])
    St = sturm(p)
    printChanges(changes(St, l, r), l, r)

print()
printLimits(l, r)<jupyter_output>Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k ≥ 1
Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k ≥ 8
Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k ≥ 1
Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k > 0
Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k ≥ 1
Number of zeros for 2/9/(k + 1/3) < ⍺ ≤ (k + 2/9)/(k + 1/3): 0 for k ≥ 1

2/9/(k + 1/3) → 0 for k → ∞
(k + 2/9)/(k + 1/3) → 1 for k → ∞<jupyter_text>There is one node more important than node 0 after adding the edge when $\alpha=\frac23$.<jupyter_code>for i in range(7):
    if i == 0:
        continue
    p = S(r_post[i] - r_post[0])
    if p == 0:
        print("Node", i, "has the same score of node 0")
    else:
        try:
            kmin = lower_bound(solve(p(a=2/3)(k=x)>0,x))
            print("Node", i, "is ultimately more important than node 0 for k", kmin)
        except:
            print("Node", i, "is ultimately not more important than node 0")<jupyter_output>Node 1 is ultimately not more important than node 0
Node 2 is ultimately not more important than node 0
Node 3 is ultimately not more important than node 0
Node 4 is ultimately more important than node 0 for k ≥ 5
Node 5 is ultimately not more important than node 0
Node 6 is ultimately not more important than node 0<jupyter_text>There is one node more important than node 0 also when $\frac23-\frac{2\sqrt k}{3\sqrt k+10}<\alpha\leq \frac23 + \frac k{3k+1}$.<jupyter_code># Here x = √k

l, r = 2/3 - 2*x/(3*x+10), 2/3 + x^2/(3*x^2+1)

for i in range(7):
    if i == 0:
        continue
    p = S(r_post[i] - r_post[0])
    St = sturm(p)
    printChanges(changes(St, l, r, power=2), l, r)

print()
printLimits(l(x=k), r(x=k))<jupyter_output>Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 18
Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 7
Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 20
Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 1
Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 23
Number of zeros for -2*x/(3*x + 10) + 2/3 < ⍺ ≤ x^2/(3*x^2 + 1) + 2/3: 0 for k ≥ 14

-2*k/(3*k + 10) + 2/3 → 0 for k → ∞
k^2/(3*k^2 + 1) + 2/3 → 1 for k → ∞<jupyter_text>NetworkX Graphs<jupyter_code>def getGH(kk):
    """
        Returns the networkx graphs of $G_k$ and $G_k'$.
        
        Args:
            the value of k
            
        Returns:
            the graph $G_k$, the graph $G_k'$ and a dictionary whose keys are the nodes of the graph and whose values
            are the node names suitable to be passed to the draw function.
    """
    labels={}
    G=nx.Graph()
    #Vertices
    for i in [0,1,2,4]:
        G.add_node(i)
        labels[i] = i
    for i in range(kk):
        G.add_node("3_{}".format(i))
        labels["3_{}".format(i)] = 3
        G.add_node("5_{}".format(i))
        labels["5_{}".format(i)] = 5
        G.add_node("6_{}".format(i))
        labels["6_{}".format(i)] = 6
    #Edges
    for i in range(kk):
        G.add_edge("3_{}".format(i), 0)
        G.add_edge("5_{}".format(i), 4)
        G.add_edge("6_{}".format(i), 1)
        G.add_edge("6_{}".format(i), 2)
        for j in range(i+1, kk):
            G.add_edge("6_{}".format(i), "6_{}".format(j))
    G.add_edges_from([(0,2), (2,4), (2,1)])
    H=G.copy()
    H.add_edge(0,1,color='r')
    return G, H, labels<jupyter_output><empty_output><jupyter_text>Let's try to compute explicitly PageRank values for given values of $k$ and $\alpha$.<jupyter_code>kk=5
aa=0.7
G,H,labels=getGH(kk)
nx.draw(H, nx.kamada_kawai_layout(H), with_labels=True, labels=labels, node_color=["red"]*2+["lightblue"]*(len(H)-2))<jupyter_output><empty_output><jupyter_text>Check that this is equivalent to its symbolic counterpart.<jupyter_code>numeric_pre = nx.pagerank(G, alpha=aa, tol=1E-10, max_iter=10000)
numeric_post = nx.pagerank(H, alpha=aa, tol=1E-10, max_iter=10000)
for xx in G.nodes():
    expected = ((1 - a) * r_pre[labels[xx]] / det_pre / G.number_of_nodes())(k=kk)(a=aa)
    actual = numeric_pre[xx]
    assert abs(float(expected-actual)) < 1E-9, "{}: {} vs. {}".format(xx, expected, actual)
    expected = ((1 - a) * r_post[labels[xx]] / det_post / G.number_of_nodes())(k=kk)(a=aa)
    actual = numeric_post[xx]
    assert abs(float(expected-actual)) < 1E-9,"{}: {} vs. {}".format(xx, expected, actual)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.20618556701030927, 'fraction_numerical': 0.08041237113402062, 'mean_word_length': 3.0099896658629004, 'pattern_counts': {'":': 0, '<': 90, '<?xml version=': 0, '>': 98, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '18', 'dir': 'jupyter-structured-clean-dedup', 'id': '565149', 'license': 'CC0-1.0', 'n_tokens_mistral': 5859, 'n_tokens_neox': 5282, 'n_words': 1525, 'path': 'pagerank-top.ipynb', 'repo_name': 'vigna/monotoniciy', 'size': '11640'}