How to interpret the results of LAP with GAE

[JackyYangPassion]

Describe the bug
DataSet
Vertices

id
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Edges

from,to
2,6
0,16
0,11
0,4
3,13
0,7
0,14
0,10
1,17
2,5
3,9
2,8
9,15
2,12

when run lpa

# 查看算法结果
# run builtin applications
result_lpa = graphscope.lpa(sub_graph_with_path)
result_lpa.to_dataframe({"node": "v.id", "result": "r"})

the result:

Use networkX
Original Graph before clustering.

Results after clustering.

Expected behavior
I want to know how can get the result like networkX with graphScope lpa

for example
community 0 [node_list]
community 1 [node_list]
.....
community n [node_list]

Environment (please complete the following information):

• GraphScope version: 0.20.0
• OS: linux

[siyuan0322]

Since the result of lpa is a pandas DataFrame, you could make some manipulations over it. For example, extract the nodes that related to a certain community like this:

communities = {}
for row in df.iterrows():
    node_id, community_id = row[1]
    if community_id not in communities:
        communities[community_id] = []
    communities[community_id].append(node_id)

for k, v in communities.items():
    print('community {}: {}'.format(k, v))

[siyuan0322]

By the way, it's pretty suitable to use chatGPT-like tools to do these jobs. 🤣

[JackyYangPassion]

Yes, I consulted with Chat-GPT while writing the issue!

Although there were some errors, it ran after the modifications were made.

[JackyYangPassion]

the result

[siyuan0322]

It seems the result is not correct, according to the edge lists, do you mean this?

[JackyYangPassion]

Yes!
First

[0,4,7,10,11,14,16] should in the same community
 but [10],[11],[14] belong to different community

Second

  community_id should Increment from 0
  community 0 []
  community 1 []
  ......

[siyuan0322]

Thanks, we will try to confirm and debug that. Sorry for the inconvenience.

[JackyYangPassion]

From the discussion #1498 cdlp = lpa in graphscope
What's the difference between networkX lpa and graphscope lpa?

[siyuan0322]

graphscope lpa is the version that we implement for LDBC benchmark, which optimized for speed.
networkx lpa is trying to be compatible with networkx native lpa.

[siyuan0322]

@JackyYangPassion 经过调查，发现原因

1. 我们这里的 CDLP 是根据 LDBC 的要求实现，实现细节可以参考 这里 的 CDLP 一节。我在这大概讲一下过程：
2. 第一轮0号点的label初始化为0，4初始化为4；第二轮0的所有邻居都把label更新为0，但0号点的邻居里，label最小的是4（不和自身的label比较），所以它把自己的label更新为4，再之后，0的邻居实际上每轮都用0号点的label更新自己（不需要比较大小，只有0一个邻居），所以刚好也是0和4交替，只不过跟0号点相反。其实就是 label互相抖动，一个最小复现的case 就是两个点直接相连的情况。

可以配置 cdlp(g,directed=False, max_round=99) cdlp(g,directed=False, max_round=100) 来看一下区别。其中 directed 指定无向图，max_round 指定最大轮数。

[JackyYangPassion]

感谢，这个修复起来容易吗？可以指导下修复

[siyuan0322]

我看一下 GS 有没有其他实现

[siyuan0322]

研究了一些 networkx 的这个lpa 的版本，发现实现上有一些区别，比如这个 asyn_lpa_communities 是不确定性的。我理解震荡会在一些特殊的节点内发生，这时由于每一轮迭代双方节点互换，所以达不到一个稳定状态。而且分布式比单机算法更加复杂一些，不容易收敛。这个如果数据量级大了之后应该不是什么问题。
另外，如果是找community 按您目前的需求感觉 cc 算法更合适一些，这个能给你想要的结果。

[JackyYangPassion]

好的 感谢建议，我试试

[JackyYangPassion]

研究了一些 networkx 的这个lpa 的版本，发现实现上有一些区别，比如这个 asyn_lpa_communities 是不确定性的。我理解震荡会在一些特殊的节点内发生，这时由于每一轮迭代双方节点互换，所以达不到一个稳定状态。而且分布式比单机算法更加复杂一些，不容易收敛。这个如果数据量级大了之后应该不是什么问题。 另外，如果是找community 按您目前的需求感觉 cc 算法更合适一些，这个能给你想要的结果。

“cc 算法” 是指 wcc?

[siyuan0322]

“cc 算法” 是指 wcc?

是的

[JackyYangPassion]

Mark After this period of study in the field of graph mining, I have a better understanding.