giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sebastian Schelter <...@apache.org>
Subject Re: About LineRank algo ..
Date Mon, 20 Jan 2014 19:09:22 GMT
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 <ssc@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 <ssc@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 <ssc@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
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>


Mime
View raw message