You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@giraph.apache.org by Jyoti Yadav <ra...@gmail.com> on 2014/01/20 08:11:11 UTC
About LineRank algo ..
Hi..
Is there anyone who is working with linerank algorithm??
Thanks
Jyoti
Re: About LineRank algo ..
Posted by Sebastian Schelter <ss...@apache.org>.
Hi Jyoti,
I'll put the files inline for simplicity. Let me know if you have
anymore questions.
--sebastian
------------------------------------------------------------------------------
FILE: linerank.m
------------------------------------------------------------------------------
load source_incidence.csv
load target_incidence.csv
S = spconvert(source_incidence);
T = spconvert(target_incidence);
n = 10;
m = 19;
d1 = S' * ones(m, 1);
d2 = T * d1;
d = 1 ./ d2;
v = rand(m, 1);
r = ones(m, 1) / m;
diff = 1;
while diff > 0.00001
v1 = d .* v;
v2 = S' * v1;
v3 = T * v2;
v_next = .85 * v3 + .15 * r;
diff = norm(v - v_next, 2);
v = v_next;
end
lineranks = (S + T)' * v;
lineranks
------------------------------------------------------------------------------
------------------------------------------------------------------------------
FILE: source_incidence.csv
------------------------------------------------------------------------------
1 1 1
2 1 1
3 1 1
4 2 1
5 3 1
6 3 1
7 3 1
8 4 1
9 4 1
10 4 1
11 5 1
12 6 1
13 6 1
14 7 1
15 8 1
16 8 1
17 9 1
18 10 1
19 10 1
------------------------------------------------------------------------------
------------------------------------------------------------------------------
FILE: target_incidence.csv
------------------------------------------------------------------------------
1 1 1
2 3 1
3 4 1
4 2 1
5 1 1
6 3 1
7 4 1
8 3 1
9 4 1
10 7 1
11 5 1
12 2 1
13 6 1
14 7 1
15 4 1
16 8 1
17 9 1
18 4 1
19 10 1
------------------------------------------------------------------------------
On 01/20/2014 05:07 PM, Jyoti Yadav wrote:
> Thanks Sebastian..
> You pls send your code,I will also check where i went wrong..
>
>
>
>
> On Mon, Jan 20, 2014 at 8:51 PM, Sebastian Schelter <ss...@apache.org> wrote:
>
>> On 01/20/2014 11:48 AM, Jyoti Yadav wrote:
>>
>>> Hi Sebastian...
>>>
>>> while referring the paper,paper talks about the normalization of L(G)
>>> matrix..Below is the few lines from the paper which talks about it..
>>>
>>>
>>> Computing Normalization Factors. The ith element of the
>>> diagonal matrix D contains the sum of ith column of L(G).
>>> D is used to column-normalize L(G) so that the resulting
>>> matrix can be used for the power iteration. The ’./’ in line 5
>>> represents the element-wise inverse operation.
>>>
>>
>> Ah I see. You're right conceptually this is the same as normalizing L(G),
>> although this is not explicitly done in Algorithm 2 shown in the paper.
>>
>>
>>
>>>
>>> One more question...
>>>
>>> Is LineRank algo is applicable to undirected and weighted graph?
>>>
>>
>> The paper explicitly mentions that LineRank is applicable to weighted
>> graphs. Furthermore, you can transform any undirected to a directed graph
>> by substituting an undirected edge by two directed ones.
>>
>> Regarding your problems with convergence, I can give you access to my
>> matlab code and some toy data that it converges on, so that you can test
>> your implementation.
>>
>> --sebastian
>>
>>
>>
>>
>>> Thanks
>>>
>>>
>>>
>>>
>>> On Mon, Jan 20, 2014 at 2:40 PM, Sebastian Schelter <ss...@apache.org>
>>> wrote:
>>>
>>> Jyoti,
>>>>
>>>> We started with a Matlab implementation on a small example graph and saw
>>>> the algorithm converge. I don't think that the paper mentions that you
>>>> have
>>>> to normalize the matrix in a certain way.
>>>>
>>>> In the standard power iteration, the vector that estimates the principal
>>>> eigenvector has to be rescaled to unit length. IIRC this is also done in
>>>> the LineRank algorithm in the paper.
>>>>
>>>> --sebastian
>>>>
>>>>
>>>>
>>>> On 01/20/2014 10:04 AM, Jyoti Yadav wrote:
>>>>
>>>> Hi Sebastian..
>>>>> I code this algorithm,but while running,it is not converging..
>>>>> One more question,for power iteration.is it necessary to column
>>>>> normalize
>>>>> the matrix or we can work with row normalized matrix?
>>>>>
>>>>> Thanks
>>>>> Jyoti
>>>>>
>>>>>
>>>>> On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org>
>>>>> wrote:
>>>>>
>>>>> I have a student working on an implementation, do you have questions?
>>>>>
>>>>>>
>>>>>>
>>>>>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>>>>>
>>>>>> Hi..
>>>>>>
>>>>>>> Is there anyone who is working with linerank algorithm??
>>>>>>>
>>>>>>> Thanks
>>>>>>> Jyoti
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
Re: About LineRank algo ..
Posted by Jyoti Yadav <ra...@gmail.com>.
Thanks Sebastian..
You pls send your code,I will also check where i went wrong..
On Mon, Jan 20, 2014 at 8:51 PM, Sebastian Schelter <ss...@apache.org> wrote:
> On 01/20/2014 11:48 AM, Jyoti Yadav wrote:
>
>> Hi Sebastian...
>>
>> while referring the paper,paper talks about the normalization of L(G)
>> matrix..Below is the few lines from the paper which talks about it..
>>
>>
>> Computing Normalization Factors. The ith element of the
>> diagonal matrix D contains the sum of ith column of L(G).
>> D is used to column-normalize L(G) so that the resulting
>> matrix can be used for the power iteration. The ’./’ in line 5
>> represents the element-wise inverse operation.
>>
>
> Ah I see. You're right conceptually this is the same as normalizing L(G),
> although this is not explicitly done in Algorithm 2 shown in the paper.
>
>
>
>>
>> One more question...
>>
>> Is LineRank algo is applicable to undirected and weighted graph?
>>
>
> The paper explicitly mentions that LineRank is applicable to weighted
> graphs. Furthermore, you can transform any undirected to a directed graph
> by substituting an undirected edge by two directed ones.
>
> Regarding your problems with convergence, I can give you access to my
> matlab code and some toy data that it converges on, so that you can test
> your implementation.
>
> --sebastian
>
>
>
>
>> Thanks
>>
>>
>>
>>
>> On Mon, Jan 20, 2014 at 2:40 PM, Sebastian Schelter <ss...@apache.org>
>> wrote:
>>
>> Jyoti,
>>>
>>> We started with a Matlab implementation on a small example graph and saw
>>> the algorithm converge. I don't think that the paper mentions that you
>>> have
>>> to normalize the matrix in a certain way.
>>>
>>> In the standard power iteration, the vector that estimates the principal
>>> eigenvector has to be rescaled to unit length. IIRC this is also done in
>>> the LineRank algorithm in the paper.
>>>
>>> --sebastian
>>>
>>>
>>>
>>> On 01/20/2014 10:04 AM, Jyoti Yadav wrote:
>>>
>>> Hi Sebastian..
>>>> I code this algorithm,but while running,it is not converging..
>>>> One more question,for power iteration.is it necessary to column
>>>> normalize
>>>> the matrix or we can work with row normalized matrix?
>>>>
>>>> Thanks
>>>> Jyoti
>>>>
>>>>
>>>> On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org>
>>>> wrote:
>>>>
>>>> I have a student working on an implementation, do you have questions?
>>>>
>>>>>
>>>>>
>>>>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>>>>
>>>>> Hi..
>>>>>
>>>>>> Is there anyone who is working with linerank algorithm??
>>>>>>
>>>>>> Thanks
>>>>>> Jyoti
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
Re: About LineRank algo ..
Posted by Sebastian Schelter <ss...@apache.org>.
On 01/20/2014 11:48 AM, Jyoti Yadav wrote:
> Hi Sebastian...
>
> while referring the paper,paper talks about the normalization of L(G)
> matrix..Below is the few lines from the paper which talks about it..
>
>
> Computing Normalization Factors. The ith element of the
> diagonal matrix D contains the sum of ith column of L(G).
> D is used to column-normalize L(G) so that the resulting
> matrix can be used for the power iteration. The ’./’ in line 5
> represents the element-wise inverse operation.
Ah I see. You're right conceptually this is the same as normalizing
L(G), although this is not explicitly done in Algorithm 2 shown in the
paper.
>
>
> One more question...
>
> Is LineRank algo is applicable to undirected and weighted graph?
The paper explicitly mentions that LineRank is applicable to weighted
graphs. Furthermore, you can transform any undirected to a directed
graph by substituting an undirected edge by two directed ones.
Regarding your problems with convergence, I can give you access to my
matlab code and some toy data that it converges on, so that you can test
your implementation.
--sebastian
>
> Thanks
>
>
>
>
> On Mon, Jan 20, 2014 at 2:40 PM, Sebastian Schelter <ss...@apache.org> wrote:
>
>> Jyoti,
>>
>> We started with a Matlab implementation on a small example graph and saw
>> the algorithm converge. I don't think that the paper mentions that you have
>> to normalize the matrix in a certain way.
>>
>> In the standard power iteration, the vector that estimates the principal
>> eigenvector has to be rescaled to unit length. IIRC this is also done in
>> the LineRank algorithm in the paper.
>>
>> --sebastian
>>
>>
>>
>> On 01/20/2014 10:04 AM, Jyoti Yadav wrote:
>>
>>> Hi Sebastian..
>>> I code this algorithm,but while running,it is not converging..
>>> One more question,for power iteration.is it necessary to column normalize
>>> the matrix or we can work with row normalized matrix?
>>>
>>> Thanks
>>> Jyoti
>>>
>>>
>>> On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org>
>>> wrote:
>>>
>>> I have a student working on an implementation, do you have questions?
>>>>
>>>>
>>>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>>>
>>>> Hi..
>>>>> Is there anyone who is working with linerank algorithm??
>>>>>
>>>>> Thanks
>>>>> Jyoti
>>>>>
>>>>>
>>>>>
>>>>
>>>
>>
>
Re: About LineRank algo ..
Posted by Jyoti Yadav <ra...@gmail.com>.
Hi Sebastian...
while referring the paper,paper talks about the normalization of L(G)
matrix..Below is the few lines from the paper which talks about it..
Computing Normalization Factors. The ith element of the
diagonal matrix D contains the sum of ith column of L(G).
D is used to column-normalize L(G) so that the resulting
matrix can be used for the power iteration. The ’./’ in line 5
represents the element-wise inverse operation.
One more question...
Is LineRank algo is applicable to undirected and weighted graph?
Thanks
On Mon, Jan 20, 2014 at 2:40 PM, Sebastian Schelter <ss...@apache.org> wrote:
> Jyoti,
>
> We started with a Matlab implementation on a small example graph and saw
> the algorithm converge. I don't think that the paper mentions that you have
> to normalize the matrix in a certain way.
>
> In the standard power iteration, the vector that estimates the principal
> eigenvector has to be rescaled to unit length. IIRC this is also done in
> the LineRank algorithm in the paper.
>
> --sebastian
>
>
>
> On 01/20/2014 10:04 AM, Jyoti Yadav wrote:
>
>> Hi Sebastian..
>> I code this algorithm,but while running,it is not converging..
>> One more question,for power iteration.is it necessary to column normalize
>> the matrix or we can work with row normalized matrix?
>>
>> Thanks
>> Jyoti
>>
>>
>> On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org>
>> wrote:
>>
>> I have a student working on an implementation, do you have questions?
>>>
>>>
>>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>>
>>> Hi..
>>>> Is there anyone who is working with linerank algorithm??
>>>>
>>>> Thanks
>>>> Jyoti
>>>>
>>>>
>>>>
>>>
>>
>
Re: About LineRank algo ..
Posted by Sebastian Schelter <ss...@apache.org>.
Jyoti,
We started with a Matlab implementation on a small example graph and saw
the algorithm converge. I don't think that the paper mentions that you
have to normalize the matrix in a certain way.
In the standard power iteration, the vector that estimates the principal
eigenvector has to be rescaled to unit length. IIRC this is also done in
the LineRank algorithm in the paper.
--sebastian
On 01/20/2014 10:04 AM, Jyoti Yadav wrote:
> Hi Sebastian..
> I code this algorithm,but while running,it is not converging..
> One more question,for power iteration.is it necessary to column normalize
> the matrix or we can work with row normalized matrix?
>
> Thanks
> Jyoti
>
>
> On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org> wrote:
>
>> I have a student working on an implementation, do you have questions?
>>
>>
>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>
>>> Hi..
>>> Is there anyone who is working with linerank algorithm??
>>>
>>> Thanks
>>> Jyoti
>>>
>>>
>>
>
Re: About LineRank algo ..
Posted by Jyoti Yadav <ra...@gmail.com>.
Hi Sebastian..
I code this algorithm,but while running,it is not converging..
One more question,for power iteration.is it necessary to column normalize
the matrix or we can work with row normalized matrix?
Thanks
Jyoti
On Mon, Jan 20, 2014 at 1:45 PM, Sebastian Schelter <ss...@apache.org> wrote:
> I have a student working on an implementation, do you have questions?
>
>
> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>
>> Hi..
>> Is there anyone who is working with linerank algorithm??
>>
>> Thanks
>> Jyoti
>>
>>
>
Re: About LineRank algo ..
Posted by Sebastian Schelter <ss...@apache.org>.
Sure :)
On 01/20/2014 09:39 AM, Claudio Martella wrote:
> do you plan to share it when you're done? :)
>
>
> On Mon, Jan 20, 2014 at 9:15 AM, Sebastian Schelter <ss...@apache.org> wrote:
>
>> I have a student working on an implementation, do you have questions?
>>
>>
>> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>>
>>> Hi..
>>> Is there anyone who is working with linerank algorithm??
>>>
>>> Thanks
>>> Jyoti
>>>
>>>
>>
>
>
Re: About LineRank algo ..
Posted by Claudio Martella <cl...@gmail.com>.
do you plan to share it when you're done? :)
On Mon, Jan 20, 2014 at 9:15 AM, Sebastian Schelter <ss...@apache.org> wrote:
> I have a student working on an implementation, do you have questions?
>
>
> On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
>
>> Hi..
>> Is there anyone who is working with linerank algorithm??
>>
>> Thanks
>> Jyoti
>>
>>
>
--
Claudio Martella
claudio.martella@gmail.com
Re: About LineRank algo ..
Posted by Sebastian Schelter <ss...@apache.org>.
I have a student working on an implementation, do you have questions?
On 01/20/2014 08:11 AM, Jyoti Yadav wrote:
> Hi..
> Is there anyone who is working with linerank algorithm??
>
> Thanks
> Jyoti
>