3
$\begingroup$

Suppose that the Wikipedia directed graph of internal links is given as below ( Starting with the article "Automobil" / Auto in German and then following at most 3 internal links in the first sentence of the article.)

In natural language processing typically one assings to words or text a vector to represent the meaning of the the word / text.

Usually when one reads a wikipedia article, one clicks to outgoing internal links to get an understanding of the words which this article is referring to.

So having this in mind I want to assign vectors to wikipedia articles in this way:

If $v$ is a wikipedia article then the meaning of this article depends on the other $N$ internal articles this article $v$ is referring to:

$$v = \frac{1}{N} \sum_{ v \rightarrow w } w$$

For an article which does not have outgoing links, we assign a new standard basis vector.

  1. My mathematical question, is if it is possible to assign vectors $v$ such that for any given directed graph structure $G$, the last equation is valid. ( I have tested this with random graphs, and it seems to be possible)

  2. Second question: Is there a fast method to solve this problem?

If this is possible, then one could add "words" (the corresponding vectors) to change the meaning of the added words. For example, for the graph below we have:

vAuto == r6
vMotor == r3
vKraftfahrzeug == 1/2*r3 + 1/2*r5
vStrassenfahrzeug == -3/2*r3 - 1/2*r5 + 3*r6
vArbeit == 1/2*r1 + 1/2*r2
vKraftmaschine == -1/2*r1 - 1/2*r2 + 2*r3
vFahrzeug == r5
vOberbegriff == 2*r5 - r8
vVerkehrsmittel == r8
vLandfahrzeug == -3*r3 - r5 + 6*r6 - r7
vStrassen == r7
vLand == -6*r3 - 3*r5 + 12*r6 - 2*r7
vLandfläche == -r4 + 2*r7
vVerkehrsbauwerk == r4
vMaschine == -r1 - 2*r2 + 4*r3
vEnergie == r2
vPhysik == r1

So for example "Work = 1/2 Energy + 1/2 Physics".

If we have a new text $T$ which contains words which correspond to wikipedia articles, then one could simply add these articles in a weighted form, an have a meaning for this text.

Thanks for your help.

example graph

Example Graph in Sagemath and "solution"

Edit: By the accepted answer given below, here is the example graph with absorbing states implemented in SAGEMATH. The probabilities are computed as $B = NR$ as described here: https://en.wikipedia.org/wiki/Absorbing_Markov_chain.

$\endgroup$

2 Answers 2

3
$\begingroup$

Suppose there are $k$ articles $a_1,\ldots,a_k$ without links, with basis vectors $e_1,\ldots, e_k$ assigned to them respectively.

The easiest way to show this assignment can be extended to the other articles in the way that you want (in fact, uniquely) is as follows. Consider a random walk on your network, starting at some article $x$, where at each step you choose a random outgoing link from the current article and follow it. With probability $1$ this eventually gets stuck in one of $a_1,\ldots, a_k$. Let $P_x(i)$ be the probability that it gets stuck in $a_i$. Now the assignment $x\mapsto \sum_{i=1}^kP_x(i)e_i$ does what you want, since the probability of reaching $a_i$ starting from $x$ is the sum over neighbours $y$ of $x$ of the probability of going to $y$ on the first step and thence reaching $a_i$, which is just $\frac{1}{N}P_y(i)$.

$\endgroup$
5
  • 1
    $\begingroup$ Thank you for your answer. What happens if there are no articles without outgoing links? $\endgroup$ Dec 22, 2020 at 14:49
  • $\begingroup$ Another question: Is it possible to compute the probabilities in a "fast" way? $\endgroup$ Dec 22, 2020 at 14:50
  • $\begingroup$ For vertices that have no reachable sink, probability of stuck is zero. $\endgroup$
    – mihaild
    Dec 23, 2020 at 9:23
  • 1
    $\begingroup$ @mihaild True; if such vertices exist my expression assigns the zero vector to them, which still satisfies the conditions. $\endgroup$ Dec 23, 2020 at 10:23
  • $\begingroup$ @EspeciallyLime: Thanks for your help! I implemented your idea in SAGEMATH for a small example graph. $\endgroup$ Dec 23, 2020 at 12:29
1
$\begingroup$

Assume we have $n$ articles without outgoing links and $m$ with them. We will show that we can assign $n$-dimensional vector to each article satisfying your conditions.

First, assign vector $e_i$ to $i$-th article without outgoing links. Each possible assignment of vectors to remaining $m$ articles can be thought as point in $\mathbb R^{m \times n}$. We will consider only assignments such that each coordinate is in segment $[0, 1]$ - corresponding points in $\mathbb R^{m \times n}$ are $[0, 1]^{m \times n}$ - a unit cube, which is a convex compact.

Now, consider standard iteration - function $F: [0, 1]^{m \times n} \to [0, 1]^{m \times n}$ given by following rule: $$F(x_1, x_2, \ldots, x_{n + m})_i = \begin{cases} e_i,\ i \leq n\\ \frac{1}{N_i} \sum\limits_{j: v_i \to v_j} x_j \end{cases}$$

Informally, $F$ just naively updates each vector independently, so it would be correct if we didn't update others.

Fixed points of $F$ are exactly valid assignments. And by Brouwer theorem, $F$ has a fixed point as a continuous function on a compact set.

Now, as we know that there is a solution, we can apply any standard method to solve linear system (it's probably sparse, which can be taken advantage of).

$\endgroup$
1
  • $\begingroup$ Thank you for your answer! (+1) $\endgroup$ Dec 23, 2020 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.