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 15:21:44 GMT
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