Re: [igraph] label propagation community

[Lin Freeman]

Tamas,

I have tried various formats on a small data set.  I'm afraid that I don't understand the different answers.  They seem to depend on the order of commands.  Here's my record.  Please help me to understand what is going on.  Thank you.  Lin

> G <- read.graph("dav1n.txt", format="ncol")
> label.propagation.community(G)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> G
Vertices: 18 
Edges: 139 
Directed: FALSE 
Edges:
                  
[0]   '1'  -- '2' 
[1]   '1'  -- '3' 
[2]   '1'  -- '4' 
[3]   '1'  -- '5' 
[4]   '1'  -- '6' 
[5]   '1'  -- '7' 
[6]   '1'  -- '8' 
[7]   '1'  -- '9' 
[8]   '1'  -- '10'
[9]   '1'  -- '11'
[10]  '1'  -- '12'
[11]  '1'  -- '13'
[12]  '1'  -- '14'
[13]  '1'  -- '15'
[14]  '1'  -- '16'
[15]  '1'  -- '17'
[16]  '1'  -- '18'
[17]  '2'  -- '3' 
[18]  '2'  -- '4' 
[19]  '2'  -- '5' 
[20]  '2'  -- '6' 
[21]  '2'  -- '7' 
[22]  '2'  -- '8' 
[23]  '2'  -- '9' 
[24]  '2'  -- '10'
[25]  '2'  -- '11'
[26]  '2'  -- '12'
[27]  '2'  -- '13'
[28]  '2'  -- '14'
[29]  '2'  -- '15'
[30]  '2'  -- '16'
[31]  '3'  -- '4' 
[32]  '3'  -- '5' 
[33]  '3'  -- '6' 
[34]  '3'  -- '7' 
[35]  '3'  -- '8' 
[36]  '3'  -- '9' 
[37]  '3'  -- '10'
[38]  '3'  -- '11'
[39]  '3'  -- '12'
[40]  '3'  -- '13'
[41]  '3'  -- '14'
[42]  '3'  -- '15'
[43]  '3'  -- '16'
[44]  '3'  -- '17'
[45]  '3'  -- '18'
[46]  '4'  -- '5' 
[47]  '4'  -- '6' 
[48]  '4'  -- '7' 
[49]  '4'  -- '8' 
[50]  '4'  -- '9' 
[51]  '4'  -- '10'
[52]  '4'  -- '11'
[53]  '4'  -- '12'
[54]  '4'  -- '13'
[55]  '4'  -- '14'
[56]  '4'  -- '15'
[57]  '4'  -- '16'
[58]  '5'  -- '6' 
[59]  '5'  -- '7' 
[60]  '5'  -- '9' 
[61]  '5'  -- '10'
[62]  '5'  -- '13'
[63]  '5'  -- '14'
[64]  '5'  -- '15'
[65]  '6'  -- '7' 
[66]  '6'  -- '8' 
[67]  '6'  -- '9' 
[68]  '6'  -- '10'
[69]  '6'  -- '11'
[70]  '6'  -- '12'
[71]  '6'  -- '13'
[72]  '6'  -- '14'
[73]  '6'  -- '15'
[74]  '6'  -- '16'
[75]  '7'  -- '8' 
[76]  '7'  -- '9' 
[77]  '7'  -- '10'
[78]  '7'  -- '11'
[79]  '7'  -- '12'
[80]  '7'  -- '13'
[81]  '7'  -- '14'
[82]  '7'  -- '15'
[83]  '7'  -- '16'
[84]  '8'  -- '9' 
[85]  '8'  -- '10'
[86]  '8'  -- '11'
[87]  '8'  -- '12'
[88]  '8'  -- '13'
[89]  '8'  -- '14'
[90]  '8'  -- '15'
[91]  '8'  -- '16'
[92]  '8'  -- '17'
[93]  '8'  -- '18'
[94]  '9'  -- '10'
[95]  '9'  -- '11'
[96]  '9'  -- '12'
[97]  '9'  -- '13'
[98]  '9'  -- '14'
[99]  '9'  -- '15'
[100] '9'  -- '16'
[101] '9'  -- '17'
[102] '9'  -- '18'
[103] '10' -- '11'
[104] '10' -- '12'
[105] '10' -- '13'
[106] '10' -- '14'
[107] '10' -- '15'
[108] '10' -- '16'
[109] '10' -- '17'
[110] '10' -- '18'
[111] '11' -- '12'
[112] '11' -- '13'
[113] '11' -- '14'
[114] '11' -- '15'
[115] '11' -- '16'
[116] '11' -- '17'
[117] '11' -- '18'
[118] '12' -- '13'
[119] '12' -- '14'
[120] '12' -- '15'
[121] '12' -- '16'
[122] '12' -- '17'
[123] '12' -- '18'
[124] '13' -- '14'
[125] '13' -- '15'
[126] '13' -- '16'
[127] '13' -- '17'
[128] '13' -- '18'
[129] '14' -- '15'
[130] '14' -- '16'
[131] '14' -- '17'
[132] '14' -- '18'
[133] '15' -- '16'
[134] '15' -- '17'
[135] '15' -- '18'
[136] '16' -- '17'
[137] '16' -- '18'
[138] '17' -- '18'
> E(G)$weight
  [1] 6 7 6 3 4 3 3 3 2 2 2 2 2 1 2 1 1 6 6 3 4 4 2 3 2 1 1 2 2 2 1 6 4 4 4 3 4
 [38] 3 2 2 3 3 2 2 1 1 4 4 4 2 3 2 1 1 2 2 2 1 2 2 2 1 1 1 1 3 2 2 1 1 1 1 1 1
 [75] 1 2 3 2 1 1 2 2 2 1 2 2 2 2 2 2 1 2 1 1 3 2 2 3 2 2 2 1 1 3 3 4 3 3 2 1 1
[112] 4 4 3 3 2 1 1 6 5 3 2 1 1 6 4 2 1 1 4 1 2 2 1 1 1 1 1 2
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
> label.propagation.community(G, weights=E(G))
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G)
 [1] 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
> E(G)
Edge sequence:
              
[0]   2  -- 1 
[1]   3  -- 1 
[2]   4  -- 1 
[3]   5  -- 1 
[4]   6  -- 1 
[5]   7  -- 1 
[6]   8  -- 1 
[7]   9  -- 1 
[8]   10 -- 1 
[9]   11 -- 1 
[10]  12 -- 1 
[11]  13 -- 1 
[12]  14 -- 1 
[13]  15 -- 1 
[14]  16 -- 1 
[15]  17 -- 1 
[16]  18 -- 1 
[17]  3  -- 2 
[18]  4  -- 2 
[19]  5  -- 2 
[20]  6  -- 2 
[21]  7  -- 2 
[22]  8  -- 2 
[23]  9  -- 2 
[24]  10 -- 2 
[25]  11 -- 2 
[26]  12 -- 2 
[27]  13 -- 2 
[28]  14 -- 2 
[29]  15 -- 2 
[30]  16 -- 2 
[31]  4  -- 3 
[32]  5  -- 3 
[33]  6  -- 3 
[34]  7  -- 3 
[35]  8  -- 3 
[36]  9  -- 3 
[37]  10 -- 3 
[38]  11 -- 3 
[39]  12 -- 3 
[40]  13 -- 3 
[41]  14 -- 3 
[42]  15 -- 3 
[43]  16 -- 3 
[44]  17 -- 3 
[45]  18 -- 3 
[46]  5  -- 4 
[47]  6  -- 4 
[48]  7  -- 4 
[49]  8  -- 4 
[50]  9  -- 4 
[51]  10 -- 4 
[52]  11 -- 4 
[53]  12 -- 4 
[54]  13 -- 4 
[55]  14 -- 4 
[56]  15 -- 4 
[57]  16 -- 4 
[58]  6  -- 5 
[59]  7  -- 5 
[60]  9  -- 5 
[61]  10 -- 5 
[62]  13 -- 5 
[63]  14 -- 5 
[64]  15 -- 5 
[65]  7  -- 6 
[66]  8  -- 6 
[67]  9  -- 6 
[68]  10 -- 6 
[69]  11 -- 6 
[70]  12 -- 6 
[71]  13 -- 6 
[72]  14 -- 6 
[73]  15 -- 6 
[74]  16 -- 6 
[75]  8  -- 7 
[76]  9  -- 7 
[77]  10 -- 7 
[78]  11 -- 7 
[79]  12 -- 7 
[80]  13 -- 7 
[81]  14 -- 7 
[82]  15 -- 7 
[83]  16 -- 7 
[84]  9  -- 8 
[85]  10 -- 8 
[86]  11 -- 8 
[87]  12 -- 8 
[88]  13 -- 8 
[89]  14 -- 8 
[90]  15 -- 8 
[91]  16 -- 8 
[92]  17 -- 8 
[93]  18 -- 8 
[94]  10 -- 9 
[95]  11 -- 9 
[96]  12 -- 9 
[97]  13 -- 9 
[98]  14 -- 9 
[99]  15 -- 9 
[100] 16 -- 9 
[101] 17 -- 9 
[102] 18 -- 9 
[103] 11 -- 10
[104] 12 -- 10
[105] 13 -- 10
[106] 14 -- 10
[107] 15 -- 10
[108] 16 -- 10
[109] 17 -- 10
[110] 18 -- 10
[111] 12 -- 11
[112] 13 -- 11
[113] 14 -- 11
[114] 15 -- 11
[115] 16 -- 11
[116] 17 -- 11
[117] 18 -- 11
[118] 13 -- 12
[119] 14 -- 12
[120] 15 -- 12
[121] 16 -- 12
[122] 17 -- 12
[123] 18 -- 12
[124] 14 -- 13
[125] 15 -- 13
[126] 16 -- 13
[127] 17 -- 13
[128] 18 -- 13
[129] 15 -- 14
[130] 16 -- 14
[131] 17 -- 14
[132] 18 -- 14
[133] 16 -- 15
[134] 17 -- 15
[135] 18 -- 15
[136] 17 -- 16
[137] 18 -- 16
[138] 18 -- 17
> label.propagation.community(G, weights=NULL)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G, weights=E(G))
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> E(G)$weight
  [1] 6 7 6 3 4 3 3 3 2 2 2 2 2 1 2 1 1 6 6 3 4 4 2 3 2 1 1 2 2 2 1 6 4 4 4 3 4
 [38] 3 2 2 3 3 2 2 1 1 4 4 4 2 3 2 1 1 2 2 2 1 2 2 2 1 1 1 1 3 2 2 1 1 1 1 1 1
 [75] 1 2 3 2 1 1 2 2 2 1 2 2 2 2 2 2 1 2 1 1 3 2 2 3 2 2 2 1 1 3 3 4 3 3 2 1 1
[112] 4 4 3 3 2 1 1 6 5 3 2 1 1 6 4 2 1 1 4 1 2 2 1 1 1 1 1 2
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> G <- read.graph("dav1n.txt", format="ncol")
> E(G)$weight
  [1] 6 7 6 3 4 3 3 3 2 2 2 2 2 1 2 1 1 6 6 3 4 4 2 3 2 1 1 2 2 2 1 6 4 4 4 3 4
 [38] 3 2 2 3 3 2 2 1 1 4 4 4 2 3 2 1 1 2 2 2 1 2 2 2 1 1 1 1 3 2 2 1 1 1 1 1 1
 [75] 1 2 3 2 1 1 2 2 2 1 2 2 2 2 2 2 1 2 1 1 3 2 2 3 2 2 2 1 1 3 3 4 3 3 2 1 1
[112] 4 4 3 3 2 1 1 6 5 3 2 1 1 6 4 2 1 1 4 1 2 2 1 1 1 1 1 2
> label.propagation.community(G, weights=E(G)$weight)
 [1] 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
> label.propagation.community(G)
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
>

On Wed, Nov 10, 2010 at 1:10 AM, Tamas Nepusz <address@hidden> wrote:

Dear Prof. Freeman,

> This confuses me.  The original method must at least begin at the first step by randomly choosing among the uniquely named adjacent and equally weighted nodes.

Yes, so does our implementation. But note that nodes are not weighted here, only the *edges* have weights, and a new label of a node is decided by weighting the neighbors' labels with the weights of the edges leading to that neighbor.

For instance, let us assume that node A has three incident edges with weights 1, 2 and 4, and leading to nodes B, C, and D, respectively. Nodes B and C are "red", node D is "blue". Node A will find that the total weight of edges leading to red nodes is 1+2=3, while the total weight of edges leading to blue nodes is 4, hence it will choose "blue" as a new label. The choice is deterministic unless there are multiple labels with equal total weights. If there is a tie among the labels with the most total weights, one of them is chosen randomly. If all the weights are equal, this reduces to the case described in the paper where the *number* of edges leading to different labels matters, not the total weight.

I hope this helps.

Regards,
--

Tamas


_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Linton C. Freeman
Institute for Mathematical Behavioral Sciences and
Department of Sociology
School of Social Sciences  SSPA 2143
University of California
Irvine, CA 92697-5100

Office:             (949) 824-6698
Home (CA):      (949) 494-6139
          (FL):      (941) 778-1074
Secretary:        (949) 824-3663
FAX:                (949) 824-3733