=Paper=
{{Paper
|id=Vol-1534/paper7
|storemode=property
|title=Extending the HITS Algorithm over Dioids
|pdfUrl=https://ceur-ws.org/Vol-1534/paper7.pdf
|volume=Vol-1534
|authors=Francisco J. Valverde-Albacete,Carmen Pelaez-Moreno
|dblpUrl=https://dblp.org/rec/conf/icfca/Valverde-Albacete15a
}}
==Extending the HITS Algorithm over Dioids==
https://ceur-ws.org/Vol-1534/paper7.pdf
Extending the HITS Algorithm over Dioids
Francisco J. Valverde-Albacete1? and Carmen Peláez-Moreno2
1
Departamento de Lenguajes y Sistemas Informáticos
Universidad Nacional de Educación a Distancia, c/ Juan del Rosal, 16. 28040 Madrid,
Spain fva@lsi.uned.es,franciscojvalverde@gmail.com
2
Departamento de Teorı́a de la Señal y de las Comunicaciones
Universidad Carlos III de Madrid, 28911 Leganés, Spain
carmen@tsc.uc3m.es
Abstract. In this paper we introduce extensions of Kleinberg’s Hubs
& Authorities (HITS) algorithm to calculate the influence of nodes in
a network whose adjacency matrix takes values over dioids, zerosumfree
semirings with a natural order.
We relate these extensions to both the Singular Value Problem and the
Eigen Problem of matrices in these semirings. We show the original HITS
algorithm to be a particular instance of the generic construction, but also
the advantages of working in idempotent semifields.
We also make some connections with extended K-Formal Concept Anal-
ysis, where the particular kind of dioid is an idempotent semifield, and
conclude that the type of knowledge extracted from a matrix by one
procedure and the other are different.
1 Introduction
The Singular Value Decomposition (SVD) [1] is a set of results about the de-
composition of a rectangular matrix with applications in data processing, signal
theory, machine learning and computer science at large.
In particular, it is a crucial tool in the dual-projection approach to the anal-
ysis of bipartite networks—also known as 2-mode, affiliation or membership net-
works [2]. The dual projection approach postulates we can provide measures of
centrality, core-vs.-periphery and structural equivalence for each of the projec-
tion networks with limited loss of global information, in terms of the left and
right singular vectors.
On the other hand, one of the first well-known approaches to link analysis
on the Web, the Hubs and Authorities algorithm or Hyperlink-Induced Topic
Search (HITS) [3, 4] also stems from the SVD. HITS was designed to solve the
problem of ranking the nodes of a dynamic, directed 1-mode network of nodes
obtained from a query against a search engine. It postulates the existence of two
qualities in nodes: their “authoritativeness”—their quality of being authorities
?
CPM has been supported by the Spanish Government-Comisión Interministerial de
Ciencia y Tecnologı́a project TEC2011-26807.
with respect to a pervasive topic in the nodes—and their “hubness”—their qual-
ity of being good pointers to authorities—and solves this in terms of the left and
right eigenvalues, again.
1.1 The original HITS formulation
Consider a directed graph D = (V, E), where V = {vi }ni=1 is a set of nodes and
E ⊆ V × V is a set of edges. It can alternatively be defined by an adjacency
matrix AD with 0 − 1 weights in its edges, (AD )ij = 1 if (vi , vj ) ∈ E and
(AD )ij = 0 otherwise. Note that this procedure can be reversed to obtain the
digraph induced by a matrix A as DA = (n, EA ) where n = {1, . . . , n} and
EA = {(i, j) | Aij = 1} .
Also note that the vertices and edges of the digraph model the nodes and links
in any social network. Precisely based in this model, HITS finds an authority
score a(vi ) and a hub score h(vi ) for each node aggregated as vectors, based in
the following iterative procedure:
• Start with initial vector estimates h<0> and a<0> of the hub and authority
scores.
• Upgrade the scores with:
h ← Aa a ← At h (1)
so that in general, for k ≥ 1:
h = (M At )k h<0> a = (At A)k a<0>
h = (AAt )k−1 Aa<0> a = (At A)k−1 At h<0> (2)
• Since matrix A is non-negative, in general the sequences {h }k and {a }k
would diverge, so the next step is to prove that the limits:
h a
lim = h<∗> lim = a<∗> (3)
k→∞ ck k→∞ dk
exist, in which case they are eigenvectors of their respective matrices for
seemingly arbitrary c and d,
(AAt )h<∗> = ch<∗> (At A)a<∗> = da<∗> . (4)
• As long as the initial estimates do not inhabit the null space of these matrices—
making them orthogonal to h<∗> and a<∗> , respectively—the iterative pro-
cess will end up finding the principal eigenvectors. The proof of this fact
entails that the initial estimates h<0> and a<0> should be non-negative.
1.2 The generalisation over complete dioids
In this paper we generalise the setting above slightly to close the gap with the
FCA problem:
1. First, as suggested by the form of (2), we consider directed weighted bipartite
graphs between two sets G and M , because we want to study the quality of
being a hub and being an authority separately.
2. Second, we consider edge weights R ∈ DG×M in a naturally ordered semir-
ing or dioid D (cfr. §2.1) . This implies passing from directed graphs to net-
works, that is weighted directed graphs. Then D-formal contexts, denoted
as (G, M, R), are a natural encoding for this type of bipartite graphs.
Note that the original HITS setting can be recovered by using G = M = V and
A = R and working in the S ∼ = R+
0 semifield with Rij = 1 if (vi , vj ) ∈ E and
Rij = 0 otherwise. Similarly, the original dual-projection approach deals only
with the case where R is actually binary but is considered to be embedded in
S∼= R+0 .
Let K = hK, ⊕, ⊗, ⊥i be a dioid. Then the space of hub scores is X = K G
and that of authorities is Y = K M and they get mutually transformed by the
actions of two linear functions:
Rt ⊗ · : K G 7→ K M R ⊗ · : K M 7→ K G
x 7→ Rt ⊗ x y 7→ R ⊗ y (5)
But we want to emphasize their mutual dependence, so after [5] we write (1)
in matrix form
h · R h
← ⊗
a Rt · a
The previous Section suggests that the solution to the HITS problem entails
t
the solution of the following eigenproblem in the variable z t = [xt y t ] ,
· R x x
B⊗z =z⊗σ ⇔ ⊗ = ⊗σ (6)
Rt · y y
where we have substituted zero matrices for dots, to lessen the visual clutter.
t
The solutions to this problem are of the form wt = [ht at ] that is, pairs of hub
and authority vectors. To see this, we expand the system (6) into two equations
called by Lanczos the “shifted eigenvalue problem” [5],
R⊗a=h⊗σ Rt ⊗ h = a ⊗ σ (7)
Equation (7) is the proof that HITS is actually trying to solve the singular value-
singular vector problem [1, 5], where h has the role of a left singular vector and
a that of a right singular vector.
To relate this problem back to the original one, we premultiply (7) by Rt ,
respectively R, to obtain
(R ⊗ Rt ) ⊗ h = h ⊗ σ ⊗2 (Rt ⊗ R) ⊗ a = a ⊗ σ ⊗2 (8)
This proves that in order to solve the HITS problem in a dioid we have to
solve the Singular Value Problem (7) which amounts to solving both decoupled
Eigenvalue Problems (8).
In this paper we develop a similar tool for bipartite networks with edges
with weights in a dioid, but we develop it as if it were an instance of the better
understood, HITS problem.
To develop our program we first introduce in Section 2.1 some definitions
and notation about semirings, in general, and about dioids and semifields, in
particular. In Section 2.2 we introduce the eigenproblem over dioids as a step to
solving the singular value problem in dioids, and in Section 2.2 a very general
technique to do so. Section 3 presents the weight of our results and we conclude
with a short Example and a Discussion.
2 Theory and Methods
2.1 Semiring and semimodules over semirings
A semiring is an algebra S = hS, ⊕, ⊗, , ei whose additive structure, hS, ⊕, i,
is a commutative monoid and whose multiplicative structure, hS\{}, ⊗, ei, is a
monoid with multiplication distributing over addition from right and left and an
additive neutral element absorbing for ⊗, i.e. ∀a ∈ S, ⊗ a = . A semiring is
commutative if its multiplication is commutative.
A semiring is zerosumfree if it does not have non-null additive factors of zero,
a ⊕ b = ⇒ a = and b = , ∀a, b ∈ S . Likewise, it is entire if a ⊗ b = ⇒
a = or b = , ∀a, b ∈ S . Entire zerosumfree semirings are called sometimes in-
formation algebras, and have abundant applications [6]. Their importance stems
from the fact that they model positive quantities.
Importantly, every commutative semiring accepts a canonical preorder, as
a ≤ b if and only if there exists c ∈ D with a ⊕ c = b which is compatible with
addition. A dioid is a commutative semiring D where this relation is actually an
order. Dioids are zerosumfree. A dioid that is also entire is a positive dioid.
An idempotent semiring is a dioid whose addition is idempotent, and a se-
lective semiring one where the arguments attaining the value of the additive
operation can be identified.
A complete semiring S [7] is a semiring where for every P (possibly infinite)
family of elements P {ai }i∈I ⊆ S we can define an element i∈I ai ∈ S such that
1. if I = ∅, then i∈I aP i = ,
2. if I = {1 . . . n}, then i∈Iai = a1 ⊕ . . . ⊕ an ,
P P P P
3. if b ∈ S, then b ⊗ i∈I ai = i∈I b ⊗ ai and i∈I ai ⊗ b = i∈I ai ⊗ b ,
and P P P
4. if {Ij }j∈J is a partition of I, then i∈I ai = j∈J i∈Ij ai .
If I is countable in the definitions above, then S is countably complete and already
zerosumfree [8, Prop. 22.28]. The importance for us is that in complete semirings,
the existence of the transitive closures is guaranteed (see below). Commutative
complete dioids are already complete residuated lattices.
A semiring whose commutative multiplicative structure is a group will be
called a semifield and radicable if the equation ab = c can be solved for a. This
term is not standard: for instance, [9] prefer to use “semiring with a multiplicative
group structure”, but we prefer semifield to shorten out statements. Semifields
are all entire. We will use K to refer to them.
A semifield which is also a dioid is both entire and naturally-ordered. These
are sometimes called positive semifields, examples of which are the positive ra-
tionals, the positive reals or the max-plus and min-plus semifields. Semifields are
all incomplete except for the booleans, but they can be completed [10], and we
will not differentiate between complete or completed structures
A semimodule over a semiring is an analogue of a vector space over a field.
Semimodules inherit from their defining semirings the qualities of being zero-
sumfree, complete or having a natural order. In fact, semimodules over com-
plete commutative dioids are also complete lattices. Rectangular matrices over
a semiring form a semimodule Mm×n (S), and in particular, row- and column-
spaces S 1×n and S n×1 . The set of square matrices Mn (S) is also a semiring (but
non-commutative unless n = 1).
2.2 The eigenvalue problem and transitive closures over dioids
Given (4), understanding the HITS iteration is easier once understood the eigen-
value problem in a semiring. So let Mn (S) be the semiring of square matrices
over a semiring S with the usual operations. Given A ∈ Mn (S) the right (left)
eigenproblem is the task of finding the right eigenvectors v ∈ S n×1 and right
eigenvalues ρ ∈ S (respectively left eigenvectors u ∈ S 1×n and left eigenvalues
λ ∈ S) satisfying:
u⊗A=λ⊗u A⊗v =v⊗ρ (9)
The left and right eigenspaces and spectra are the sets of these solutions:
Λ(A) = {λ ∈ S | Uλ (A) 6= {n }} P(A) = {ρ ∈ S | Vρ (A) 6= {n }}
Uλ (A) = {u ∈ S 1×n | u ⊗ A = λ ⊗ u} Vρ (A) = {v ∈ S n×1 | A ⊗ v = v ⊗ ρ}
[ [
U(A) = Uλ (A) V(A) = Vρ (A) (10)
λ∈Λ(A) ρ∈P(A)
Since Λ(A) = P(At ) and Uλ (A) = Vλ (At ) , from now on we will omit refer-
ences to left eigenvalues, eigenvectors and spectra, unless we want to emphasize
differences.
In order to solve (6) in dioids we have to use the following theorem [11, 9]:
Theorem 1 (Gondran and Minoux, [11, Theorem 1]). Let A ∈ S n×n . If
A∗ exists, the following two conditions are equivalent:
1. A+ ∗
.i ⊗ µ = A.i ⊗ µ for some i ∈ {1 . . . n}, and µ ∈ S.
2. A.i ⊗ µ (and A∗.i ⊗ µ) is an eigenvector of A for e , A+
+
.i ⊗ µ ∈ Ve (A) .
+
P ∞
where we defineP∞the transitive closure A = k=1 and the transitive reflexive
∗
closure A = k=0 of A (also caleld Kleene’s plus and star operators).
In [12, 13, 14] this result was made more specific in two directions: on the
one hand, by focusing on particular types of completed idempotent semirings—
semirings with a natural order where infinite additions of elements exist so tran-
sitive closures are guaranteed to exist and sets of generators can be found for
the eigenspaces—and, on the other hand, by considering more easily visualizable
subsemimodules than the whole eigenspace—a better choice for exploratory data
analysis.
From Theorem 1 it is clear that we need efficient methods to obtain the
closures. The following account is a summary of results in this respect, and we
refer the reader to [12, 13] for proofs.
Lemma 1. Let A ∈ Mn (A) be a square matrix over a commutative semiring
S. A∗ exists if and only if A+ exists and then:
A+ = A ⊗ A∗ = A∗ ⊗ A A ∗ = I ⊕ A+
But since in incomplete semirings the existence of the closures is not warranted,
our natural environment should be that of complete semirings. In dioids we have,
Lemma 2. Let A ∈ Mn (A) be a square matrix over a dioid S. For partition
n̄ = α ∪ β call Per (A) = Aβα A∗αα Aαβ ⊕ Aββ . Then
+ ∗ ∗ ∗ ∗
A+ A∗αα Aαβ Per (A)
Aαα Aαβ αα ⊕ Aαα Aαβ Per (A) Aβα Aαα
= ∗ ∗ +
Aβα Aββ Per (A) Aβα Aαα Per (A)
Proof. Adapted from [15, Lemma 4.101] t
u
Closures and simultaneous row and column permutations commute:
Lemma 3. Let A, B ∈ Mn (S) and let P be a permutation such that B = P t AP .
Then B + = P t A+ P and B ∗ = P t A∗ P .
Given the importance of the transitive closure of a matrix in the calculations
of eigenvalues and eigenvectors highlighted by Theorem 1, we use the inductive
structure of reducible matrices over dioids to calculate them. First a basic case:
A square matrix is irreducible if it cannot be simultaneously permuted into a
triangular upper (or lower) form. Otherwise we say it is reducible. Irreducibility
expresses itself as a graph property on the induced digraph DA of Section 1.1.
Lemma 4. If A ∈ Mn (S) is irreducible, then:
• The induced digraph DA has a single strongly connected component.
• All nodes in its induced digraph DA are connected by cycles.
A structure based in irreducible matrices is described next.
Lemma 5 (Recursive Upper Frobenius Normal Form, UFNF). Let A ∈
Mn (S) be a matrix over a semiring and GA its condensation digraph. Then,
1. (UFNF3 ) If A has zero lines it can be transformed by a simultaneous row
and column permutation of VA into the following form:
Eιι · · ·
· Eαα Aαβ Aαω
P3t ⊗ A ⊗ P3 = · · Aββ Aβω
(11)
· · · Eωω
where either Aαβ or Aαω or both are non-zero, and either Aαω or Aβω or
both are non-zero. Furthermore, P3 is obtained concatenating permutations
for the indices of simultaneously zero columns and rows Vι , the indices of
zero columns but non-zero rows Vα , the indices of zero rows but non-zero
columns Vω and the rest Vβ as P3 = P (Vι )P (Vα )P (Vβ )P (Vω ).
2. (UFNF2 ) If A has no zero lines it can be transformed by a simultaneous row
and column permutation P2 = P (A1 ) . . . P (Ak ) into block diagonal UFNF:
A1 · . . . ·
· A2 . . . ·
P2t ⊗ A ⊗ P2 = . . . (12)
.
.. .. . . ..
· · . . . AK
where {Ak }Kk=1 , K ≥ 1 are the matrices of connected components of GA .
3. (UFNF1 ) If A is reducible with no zero lines and a single connected compo-
nent it can be simultaneously row- and column-permuted by P1 to
A11 A12 · · · A1R
· A22 · · · A2R
P1t ⊗ A ⊗ P1 = . (13)
.. . . ..
.. . . .
· · · · · ARR
where Arr are the matrices associated to each of its R strongly connected
components (sorted in a topological ordering), and P1 = P (A11 ) . . . P (ARR ).
Note that irreducible blocks are the base case of UFNF1 , so we sometimes refer
to irreducible matrices as being in UFNF0 .
2.3 Graphs, eigenvalues and eigenvectors of matrices over complete
dioids
Graph induced by a matrix. It is interesting to consider matrices under a
different cryptomorphism: For a matrix A ∈ Mn (S), the network or weighted
digraph induced by A, NA = (VA , EA , wA ), consists of a set of vertices VA , a set
of arcs , EA = {(i, j) | Aij 6= S }, and a weight wA : VA × VA → S, (i, j) 7→
wA (i, j) = aij .
This allows us to apply intuitively all notions from networks to matrices and
+
vice versa, like the underlying graph GA = (VA , EA ), the set of paths ΠA (i, j)
+
between nodes i and j or the set of cycles CA .
Orthogonality of eigenvectors. In spectral decomposition, orthogonality
of the eigenvectors plays an important role. In zerosumfree semimodules or-
thogonality cannot be as prevalent as in standard vectors spaces. To see this,
first call the support of a vector, the set of indices of non-null coordinates
supp(v) = {i ∈ n|vi 6= }, and consider a simple lemma:
Lemma 6. In semimodules over entire, zerosumfree semirings, only vectors with
empty intersection of supports are orthogonal.
Pn
Proof. Suppose v⊥u, then i=1 vi ⊗ ui = . If any vi = or ui = then their
product is null, so we P need only consider a non-empty supp(v) ∩ supp(u) . In
this case, v t ⊗ u = i∈supp(v)∩supp(u) vi ⊗ ui . But if S is zerosumfree, for the
sum to be null every factor has to be null. And for a factor to be null, since S is
entire, either vi is null, or ui is null, and then i would not belong in the common
support. t
u
The null eigenspaces. If any, the eigenvectors of the null eigenvalue are inter-
esting in that they define the null eigenspace. Also, the particular eigenvalue ⊥
can only appear in UFNF3 . The following proposition describes the null eigen-
value and eigenspace:
Proposition 1. Let S be a semiring and A ∈ Mn (S). Then:
1. If the i-th column is zero then the characteristic vector ei is a fundamental
eigenvector of for A and ∈ Pp(A) .
2. Non-collinear eigenvectors of are orthogonal, so the order of multiplicity of
⊥ ∈ Pp(A) is the number of empty columns of A .
3. If S is entire, then GA has no cycles if and only if Pp(A) = {} .
4. If S is entire and zerosumfree, the null eigenspace if generated by the funda-
mental eigenvectors of for A, V (A) = hFEVρ() Ai .
Proof. See [12, 3.6 & 3.7]. Claim 2 is a consequence of claim 1 and Lemma 6. t
u
Note that these are important in as much as they generate ⊥ coordinates in the
eigenvectors, that is, in the hubs and authorities vectors.
Eigenvalues and eigenvectors of matrices over positive semifields.
When S has more structure we can improve on the results in the previous section.
The first proposition advises us to concentrate on the irreducible blocks:
Proposition 2. If K is a positive semifield, A ∈ Mn (K) is irreducible, and
v ∈ Vρ (A) then ρ > and ∀i ∈ n , vi > .
Proof. See [9, Lemma 4.1.2]. t
u
Note that these results apply to R+ 0 , but not to R+,× or to C+,× , since the latter
are not dioids.
For a finite ρ ∈ K in a semifield, let (Aeρ )+ = (ρ−1 ⊗ A)+ be the normalized
transitive closure of A. The lemma below allows us to change the focus from the
transitive closures to the circuit structure of GA and vice-versa.
∗
Lemma P ∈ Mn (K), then if (ρ−1 ⊗ A) exists and
7. If K is a semifield and A P
−1 l(c)
if either c∈Ci w(c) ⊗ (ρ ) ⊕ e = c∈Ci w(c) ⊗ (ρ−1 )l(c) where Ci denotes
+
the set of circuits in CA containing node vi , or
∗ +
(ρ−1 ⊗ A)·i = (ρ−1 ⊗ A)·i (14)
∗
then (ρ−1 ⊗ A)·i is an eigenvector of A for eigenvalue ρ .
Proof. See [9, Chapter 6, Corollary 2.4]. t
u
p
When K is a radicable semifield, the mean of cycle c is µ⊕ (c) = l(c)
w(c), If
the semifield is (additively) idempotent the aggregate cycle mean of A is µ⊕ (A) =
P +
{µ⊕ (c) | c ∈ CA }. If the semiring is idempotent and selective, the nodes in
the circuits that attain this mean are called the critical nodes of A, VAc = {i ∈
c | µ⊕ (c) = µ⊕ (A)}.
Then the critical nodes are VAc = {i ∈ VA | (A) e + = e}, and we define the set
ii
of (right) fundamental eigenvectors of A for ρ as
e + | i ∈ VAc } = {(A)
FEVρ(A) = {(A) e + | (A)
e + = e}.
·i ·i ii
The basic building block is the spectrum of irreducible matrices:
Theorem 2 ((Right) spectral theory for irreducible matrices, [12]). Let
A ∈ Mn (K) be an irreducible matrix over a complete commutative selective
radicable semifield. Then:
1. The right spectrum of the matrix includes the whole semiring but the zero:
P(A) = K \ {⊥}
2. The right proper spectrum only comprises the aggregate cycle mean:
Pp(A) = {µ⊕ (A)}
3. If an eigenvalue is improper ρ ∈ P(A) \ Pp(A), then its eigenspace (and
eigenlattice) is reduced to the two vectors:
Vρ (A) = {⊥n , >n } = Lρ (A)
4. The eigenspace for a finite proper eigenvalue ρ = µ⊕ (A) < > is generated
from its fundamental eigenvectors over the whole semifield, while the eigen-
lattice is generated by the semifield 3 = h{⊥, e, >}, ⊕, ⊗, ⊥, e, >i .
Vρ (A) = hFEVρ(A)iK ⊃ Lρ (A) = hFEVρ(A)i3
Note how this theorem introduces the notion of eigenlattices to finitely represent
an eigenspace over an idempotent semifield. Refer to [12] for further details.
We will see in our results that the only other UFNF type we need be con-
cerned about is UFNF2 : Let the partition of VA generating the permutation
that renders A in UFNF2 , block diagonal form, be VA = {Vk }K k=1 , and write
UK
A = k=1 Ak , Ak = A(Vk , Vk ).
UK
Lemma 8. Let A = k=1 Ak ∈ Mn (S) be a matrix in UFNF2 , over a semiring,
and Vρ (Ak ) (Uλ (Ak )) a right (left) eigenspace of Ak for ρ (λ). Then,
K K
Uλ (A) ∼
= × U (A )
k=1
λ k Vρ (A) ∼
= × V (A ).
k=1
ρ k (15)
Note that this procedure is constructive and how the combinatorial nature
of the proof in [13] makes the claim hold in any semiring. Clearly, if ρ ∈ Pp(Ak )
for any k, then ρ ∈ Pp(A). Since Pp(Ak ) = Λp(Ak ) for matrices admitting an
SK
UFNF2 , Pp(A) = Λp(A) = k=1 Pp(Ak ).
Corollary 1. Let A ∈ Mn (S) be a matrix in UFNF2 over a semiring. Then
the (left) right eigenspace of A for ρ ∈ P(A) is the product of the (left) right
eigenspaces for the blocks, Uλ (A) = ×Kk=1 Uλ(Ak ) and Vρ(A) = ×Kk=1 Vρ(Ak ).
In complete semirings, looking for generators for the eigenspaces with δk (k) =
e and δk (i) = ⊥ for k 6= i, we define the right fundamental eigenvectors as
K
" #
K
×
[
2 1
FEVρ (A) = δk (i) ⊗
FEVρ (Ai ) . (16)
k=1 i=1
Lemma 8 proves that FEV2ρ (A) ⊂ Vρ (A), but we also have,
Lemma 9. Let A ∈ Mn (D) be a matrix in UFNF2 over a complete idempotent
semiring with ρ ∈ P(A). Then,
×
h K i
1. If ρ ∈ Pp(A), then FEV2,f 1,f
S
ρ (A) = p
k|ρ∈P (Ak ) δ
i=1 k (i) ⊗
FEV ρ (A i .
)
2. If ρ ∈ P(A) \ P (A) then FEV2ρ (A) = FEV2,>(A).
p
3. If ρ ∈ Pp(A) then FEVρ(A) = FEV2,fρ (A) ∪ FEV
2,>
(A) \ > ⊗
FEV2,f
ρ (A).
2,> 2
4. FEV (A) = > ⊗
FEVρ (A).
So call FEV2,>(A) the saturated fundamental eigenvectors of A, and define
the (right) saturated eigenspace as V >(A) = hFEV2,>(A)iD .
Corollary 2. Let A ∈ Mn (S) be a matrix in UFNF2 over a complete selective
radicable idempotent semifield. Then
1. For ρ ∈ Pp(A), Vρ (A) ⊇ V >(A).
2. For ρ ∈ P(A) \ Pp(A), Vρ (A) = V >(A).
Notice that the very general proposition below is for all complete dioids.
Proposition 3. Let A ∈ Mn (D) be a matrix in UFNF2 over a complete dioid.
Then,
1. For ρ ∈ P(A) \ Pp(A),
U >(A) = hFEV2,>(At )i3 V >(A) = hFEV2,>(A)i3 .
2. For ρ ∈ Pp(A), ρ < >,
Uλ (A) = hFEV2ρ (At )iD Vρ (A) = hFEV2ρ (A)iD .
To better represent eigenspaces, we define the spectral lattices of A,
t
Lλ (A) = hFEV2ρ (At ) i3 Lρ (A) = hFEV2ρ (A)i3 .
involving the product of the component lattices, Lρ (A) = ×Kk=1 Lρ(Ak ).
3 The Hubs & Authorities algorithm over dioids
Let (G, M, R) be an S-formal context over a complete dioid S, and A ∈ Mn (S)
as in (6). Equation (6) states the solution of the singular value-singular vector
problem in dioids in terms of the eigenproblem of a symmetric matrix.
3.1 The eigenproblem in symmetric matrices
Since A is symmetric, we no longer have to worry about the distinction between
the left and right eigenproblem:
t
Lemma 10. If A is symmetric then Λp(A) = Pp(A) and (Uρ (A)) = Vρ (A) .
We can also refine the results in Proposition 1:
Proposition 4. Let S be a semiring and a symmetric A ∈ Mn (S). Then:
1. The multiplicity of ⊥ ∈ Pp(A) is the number of empty rows or columns of
A.
2. If S is entire, Pp(A) = {} if and only if A = En .
Proof. First, if A = At , then the number of empty rows and empty columns is
the same, and Proposition 1.2 provides the result. Second, after 1.3 Pp(A) = {}
means GA has no cycles. But if Aij 6= then c = i → j → i is a cycle with
non-null weight w(c) = Aij ⊗ Aji 6= , which is a contradiction. t
u
Note that empty rows of R generate left eigenvalues while empty columns gen-
erate right eigenvalues, so the multiplicity of the null singular value may change
from left to right.
To use Lemma 7 and Theorem 2, we need the maximum cycle mean:
Proposition 5. Let K be a complete idempotent semifield and let A ∈ S n be
symmetric. Then µ⊕ (A) = supi,j Aij , where the sup, taken in the natural order
of the semifield is attained.
Proof. Since A is symmetric, c = i → j → i is a cycle wheneverAij = Aji 6= ⊥ .
Then µ⊕ (c) = Aij . Consider one c0 such that µ⊕ (c0 ) = supi,j Aij = maxi,j Ai,j
in the order of the semiring. This must exist since i, j are finite. If we can extend
any of these critical cycles with another node k such that c00 = i → j → k → i
l(c00 )
then w(c00 ) = Aij ⊗ Ajk ⊗ Aki ≤ A3ij = µ⊕ (c0 ) , so in the aggregate mean
µ⊕ (c0 ) ⊕ µ⊕ (c00 ) = µP
⊕ (c0
) . So we induce on the length of any cycle that is an
extension of c0 that c∈C + = µ⊕ (c0 ) = supi,j Ai,j . t
u
A
To find the cycle means easily, we use the UFNF form.
3.2 UFNF forms of symmetric matrices and their closures
For symmetric reducible matrices, the feasible UFNF types are simplified:
Proposition 6. Let S be a dioid, and a symmetric A ∈ Mn (S). Then:
• (UFNF3 ) A admits a proper symmetric UFNF3 form if it has zero lines,
and, in that case, the set of zero lines and zero rows are the same.
t Aββ ·
P3 ⊗ A ⊗ P3 = (17)
· Eιι
• (UFNF2 ) If a A has no zero lines it can be transformed by a simultaneous
row and column permutation P2 = P (A1 ) . . . P (Ak ) into symmetric block
diagonal UFNF:
A1 · . . . ·
· A2 . . . · ]K
P2t ⊗ A ⊗ P2 = . . . = Ak (18)
.
.. .. . . ..
k=1
· · . . . AK
where {Ak }K
k=1 , K ≥ 1 are the symmetric matrices of connected components
of GA .
• (no UFNF1 ) A cannot be permuted into a proper UFNF1 form.
We will see that this is almost the only structure we need worry about.
Consider R of the form:
R1 R12
R= (19)
R21 R2
If R12 and R21 are null, then we can find P a permutation so that
· · R1 · · R1 · ·
· · · R2
⊗ P = R1 · · ·
t
Pt ⊗ A ⊗ P = Pt ⊗ R1 · · ·
t · · · R2 (20)
· R2t · · · · R2t ·
Now, if R2 = EG2 M2 is null, then (20) is in UFN3 with Eιι = E(G2 +M2 )(G2 +M2 ) ,
while if R1 and R2 are both full, then (20) is in UFN2 with blocks A1 and
A2 respectively. Other other blocked forms of R simply generate an irreducible
A, since the UFNF1 form is not possible. So we can suppose that A can be
simultaneously row and column permuted into a diagonal block form
A1 · · · · ·
.. . . .. .. K
!
t . . . .
] · Rk
P ⊗A⊗P = = Ak ] Eιι Ak = (21)
· · · · AK · Rkt ·
k=1
· · · · · Eιι
with the empty lines and rows permuted to the beginning Eιι and irreducible
blocks Ak . Recall that closures and permutations commute, whence the clo-
sures of the matrices in the forms above are really simple: the closure of (21) is
straightforward in terms of the closures of the blocks:
+
A1 · · · · ·
.. . . .. ..
P t ⊗ A+ ⊗ P = .
. . . (22)
· · · · A+ ·
K
· · · · · Eιι
The solution of this base case is highly dependent in the dioid in which the
problem is stated. Since we will be solving the problem in idempotent semifields,
for the irreducible base case we need only be concerned about matrix:
" #
· eµ⊕(A)
R · B
µ⊕(A)
A = = (23)
eµ⊕(A) )t
e
(R · Bt ·
where we are using the shorthand B = R eµ⊕(A) to account for the normalization
with the cycle means that we need to use to find the eigenvectors. To find the
closures of such irreducible matrices apply Lemma 2 to (23):
" #+
eµ⊕(A) + ∗
µ (A)
+ · R (B ⊗ B t ) B ⊗ (B t ⊗ B)
A
e ⊕ = = ∗ (24)
eµ⊕(A) )t
(R · B t ⊗ (B ⊗ B t ) (B t ⊗ B)
+
∗ ∗
where we have used that (B t ⊗ B) ⊗ B t = B t ⊗ (B ⊗ B t ) .
3.3 Pairs of singular vectors of symmetric matrices over idempotent
semifields.
To extract the eigenvectors corresponding to left singular vectors i ∈ G (respec-
tively, right singular vectors j ∈ M ) we need to check Theorem 1 against each
block in its diagonal:
∗ +
eµ⊕(A) = A eµ⊕(A) ∗ +
i ∈ G, A ⇔ (B ⊗ B t )·i = (B ⊗ B t )·i
·i ·i
∗ +
eµ⊕(A) eµ⊕(A) ∗ +
j ∈ M, A = A ⇔ (B t ⊗ B)·j = (B t ⊗ B)·j
·j ·j
+
So the existence of Aeµ⊕(A) requires the existence of the transitive closures
+ +
(B t ⊗ B) and (B ⊗ B t ) as we could have expected from (8). Note that after
(4), the hub and authority scores are those columns such that:
+ ∗ + ∗
(B ⊗ B t )·i = (B ⊗ B t )·i (B t ⊗ B)·j = (B t ⊗ B)·j
but, importantly, (24) gives us the form of the authority score related to a
particular hub score and vice-versa, which is a kind of formal-concept property:
∗ ∗
hi = (B ⊗ B t )·i ⇔ ai = B t ⊗ (B ⊗ B t )·i (25)
t ∗ ∗
aj = (B ⊗ B)·j ⇔ hj = B ⊗ (B t ⊗ B)·j (26)
This solves completely the description of the left and right singular vectors. To
find the singular values, we note from (8) that they are the square roots of the
cycle means of the independent blocks or, equally, the proper eigenvalues of A,
√ √
Σ = { ρ | ρ = µ⊕ (Ak ) , A = ⊕k Ak } = { ρ | ρ = Pp(A)}
This would include the bottom if and only if one of the blocks is empty.
4 Example
In this section we present a HITS analysis for a weighted two-mode network both
using standard HITS and HITS over the max-min-plus idempotent semifield.
The data being analysed is the example in [16, p. 31], the worries data, which
is a two-mode network of the type of worry declared as most prevalent by 1554
adult Israeli depending on their living countries—and sometimes those of their
parents. The graph of the network is depicted in Fig. 1.(a).
The “authority” and “hub” scores are differentiated for each of the modes:
they return “type of worry” and “procedence” scores, respectively. We can see
that HITS and i-HITS produce somehow different results: the actual meaning
of these differences is data-dependent and a matter for future, more specialized
analyses. The idempotent primitives were developed in-house and are available
from the authors upon request.
5 Discussion
We have generalized the HITS algorithms for semirings, then instantiated it in
dioids, semifields (including the original semifield where it was defined), and
finally in idempotent semifields.
More importantly, solving these problems entails solving the Singular value-
Singular vector problems in the semiring of choice. We have sketched the general
solution for dioids and positive semifields, and provided a complete solution in
idempotent semifields.
(a) Worries weighted bipartite network
(b) Principal worry scores (c) Procedence scores
Fig. 1: Weighted, directed graphof the worries data [16, p. 31] and its weighted
idempotent and standard hub and authority scores. There are clear differences
in both approaches.
Note that the original HITS problem was set in a positive semifield that is
not idempotent, hence our method of solution does not apply yet to that case,
but does apply to the max-min-plus and max-min-times semifields, examples of
which are given in terms of their normalized closures. In the case of the R+ 0 the
Perron-Frobenius theorem is invoked to solve HITS iteratively by means of the
power method.
A reviewer of this paper requested a consideration of the solution of the HITS
problem for the rest of dioids which are not semifields. The problem with further
generalization of our scheme is the base case for the recursion of Frobenius normal
forms. In the idempotent semifield case, the cycle means provide the eigenvalues
needed for the normalization of the matrices that allow the calculation of the
closures in the irreducible case. But in the generic positive semifield case the
cycle means and the possibility of choosing the critical circuits to select the
eigenvectors in the closures are not granted. Also, in inclines—and in the fuzzy
semirings included in them—the base, irreducible case is completely different to
that of semifields [9]. But since the generic development on dioids for UFNF1
and UFNF2 is based in combinatorial considerations, we believe that a solution
for the base case for other dioids could be plugged into this UFNF recursion to
obtain analog results to those presented here. These extensions will be considered
in future work.
On another note, the SVD in standard algebra makes a strong case about
the orthogonality of the left and right singular vectors belonging to different
singular values in order to guarantee certain properties of the bases of singular
vectors in the reconstruction. But in entire zerosumfree semirings, and in entire
dioids or positive semifields a fortiori, orthogonality is a rare phenomenon, after
Lemma 6.
Indeed, irreducible matrices do not have any orthogonal, but rather collinear
left or right singular vectors. Regarding reducible matrices, note that (21) factors
in all the possible orthogonality between eigenvectors. In fact we have,
Corollary 3. Let (G, M, R) be an S-formal context over a dioid S, and A ∈
Mn (S) as in (24). Then two of the eigenvectors for A or (left, right) singular
vectors for R can only be orthogonal only if they arise from different blocks.
and Proposition 3 proves that even in that case they might not be orthogonal.
Regarding the glimpse of a formal concept-like property of (25), a cursory
analysis with the techniques in [10], shows that the analogue of the polars in
FCA actually come from two different generalised Galois connections, so their
order-properties are not the same. Yet, the isomorphism between the ranges of
the operators in (5) defining the duality between hubs and authorities is clear
and attested in a more generic context than HITS was initially conceived.
Bibliography
[1] Strang, G.: The fundamental theorem of linear algebra. The American
Mathematical Monthly 100 (1993) 848–855
[2] Everett, M.G., Borgatti, S.P.: The dual-projection approach for two-mode
networks. Social networks 35 (2013) 204–210
[3] Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. Jour-
nal of the ACM 46 (1999) 604–632
[4] Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning
About a Highly Connected World. Cambridge University Press 2010 (2010)
[5] Lanczos, C.: Linear Differential Operators. Dover Publications (1997)
[6] Pouly, M., Kohlas, J.: Generic Inference. A Unifying Theory for Automated
Reasoning. John Wiley & Sons (2012)
[7] Golan, J.S.: Power Algebras over Semirings. With Applications in Mathe-
matics and Computer Science. Volume 488 of Mathematics and its applica-
tions. Kluwer Academic, Dordrecht, Boston, London (1999)
[8] Golan, J.S.: Semirings and their Applications. Kluwer Academic (1999)
[9] Gondran, M., Minoux, M.: Graphs, Dioids and Semirings. New Models and
Algorithms. Operations research/Computer Science Interfaces. Springer
(2008)
[10] Valverde-Albacete, F.J., Peláez-Moreno, C.: Extending conceptualisation
modes for generalised Formal Concept Analysis. Information Sciences 181
(2011) 1888–1909
[11] Gondran, M., Minoux, M.: Valeurs propres et vecteurs propres dans les
dioı̈des et leur interprétation en théorie des graphes. EDF, Bulletin de la
Direction des Etudes et Recherches, Serie C, Mathématiques Informatique
2 (1977) 25–41
[12] Valverde-Albacete, F.J., Peláez-Moreno, C.: Spectral lattices of irreducible
matrices over completed idempotent semifields. Fuzzy Sets and Systems
(2014)
[13] Valverde Albacete, F.J., Peláez-Moreno, C.: The spectra of reducible ma-
trices over completed commutative idempotent semifields and their spectral
lattices. International Journal of General Systems (Accepted for publica-
tion.)
[14] Valverde-Albacete, F.J., Peláez-Moreno, C.: Spectral lattices of reducible
matrices over completed idempotent semifields. In Ojeda-Aciego, M., Out-
rata, J., eds.: Concept Lattices and Applications (CLA 2013), Université de
la Rochelle, Laboratory L31, La Rochelle (2013) 211–224
[15] Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorems in
idempotent semimodules. Linear Algebra and Its Applications 379 (2004)
395–422
[16] Mirkin, B.: Mathematical Classification and Clustering. Volume 11 of Non-
convex Optimization and Its Applications. Kluwer Academic Publishers
(1996)