getzep
Code consultation --- About the label propagation algorithm
I am not sure if I might be misunderstanding something, but I believe there could be an issue with line 110 in community_operations.py:
new_community = max(community_candidate, curr_community)
The core idea of this algorithm is to update community_candidate based on the majority vote from its neighbors. However, if community_candidate has a higher weight but a smaller ID, wouldn’t this prevent the necessary update from being applied?
It seems to me that this line should be:
new_community = community_candidate == -1 ? curr_community : community_candidate
Since the tie-breaking logic has already been handled through sorting in line 107, using max(community_candidate, curr_community) may cause cases where an update should occur but does not.
I would appreciate your thoughts on this. Thank you for your time!
You are correct in that the max() line of logic is incorrect. However, the tie-breaking isn't completely handled by line 107 since a node could have a community shared by none of its neighbors (in particular this will during the first iteration of the algorithm).
I believe that the conditions are as follows:
- If
community_candidate == -1, we should keepcurr_community - Else if the rank of
community_candidate> 1 then we should use thecommunity_candidate. This is because the only way forcurr_communityto not be in the candidate list is for the node to not share a community with any of its neighbors. - Else if the rank of
community_candidate == 1, then we should usemax(community_candidate, current_community).
I believe the following code captures this logic: ` candidate_rank, community_candidate = community_lst[0] if len(community_lst) > 0 else (0, -1)
if community_candidate != -1 and candidate_rank > 1:
new_community = community_candidate
else:
new_community = max(community_candidate, curr_community)
`
Since you found the bug, would you like to open a PR with the fix? Otherwise I am happy to do it.
Good catch and thank you!
