Help Needed with Code Modification in the pivot selection in Degeneracy Algorithm

[Joey199875]

Hi strash,

I am writing to discuss a potential issue I have encountered while working with the DegeneracyAlgorithm.

Upon inspecting the DegeneracyAlgorithm, I noticed that if we simply modify the content of the findBestPivotNonNeighborsDegeneracy method to set all vertices in pivotNonNeighbors to be the vertices in the P set, the DegeneracyAlgorithm generates a significant number of incorrect maximal cliques, particularly including many subsets of maximal cliques.

This result looks strange, after all, if pivotNonNeighbors = P set, the enumeration result should not change in any way.

I would greatly appreciate it if you could provide an explanation for this issue or guide me on how to modify the code effectively to rectify it.

Looking forward to your insights and guidance.

Best regards,
Joey

[darrenstrash]

Thank you for reaching out. First note that I will change this issue to "help wanted" since this is not a bug. (There is no problem with the code as written.)

Do you have a fork of your changes or can otherwise tell me exactly how you updated the code? I imagine that more code needs to be changed to make your intended functionality work.

My best guess is that you are still selecting a pivot, and updating X to contain only the pivots non-neighbors. In the case where you aren't using a pivot, X should not be changed. If X is updated to include only pivot non-neighbors in this case, but P was not updated to include only pivot non-neighbors, then this might explain why non-maximal cliques (or duplicate cliques) are generated.

[Joey199875]

Thank you for your prompt response!

I trust that your code is indeed correct. It seems I may have overlooked something that led to these results.

I made changes only to the findBestPivotNonNeighborsDegeneracy method within the DegeneracyAlgorithm. Specifically, I replaced the content in the findBestPivotNonNeighborsDegeneracy method with the following code:

inline int findBestPivotNonNeighborsDegeneracy( int** pivotNonNeighbors, int* numNonNeighbors,
int* vertexSets, int* vertexLookup,
int** neighborsInP, int* numNeighbors,
int beginX, int beginP, int beginR)
{
* pivotNonNeighbors = (int*)Calloc(beginR-beginP, sizeof(int));
memcpy(*pivotNonNeighbors, &vertexSets[beginP], (beginR-beginP)*sizeof(int));
* numNonNeighbors = beginR-beginP;
return 0;
}

Then a large number of non maximal cliques appeared in the final result, also including some incorrect results. Considering that I only modified the findBestPivotNonNeighborsDegeneracy method, I likely did not involve the parts related to updating the X and P sets. If my understanding is incorrect, I would appreciate your guidance and correction!

Thank you for your assistance!

Best regards,
Joey

[darrenstrash]

At a first glance, I don't see any issues with your change. Can you please attach a (small) data set where you get incorrect results? Together with text of a) the expected output and b) the output you are getting with your change. I can then test and see what is happening.

Note that I won't have time to debug this today, but I should be able to reply in the next week.

[Joey199875]

Thank you for your assistance!

The dataset I'm using is the biogrid-mouse dataset from your project. I have attached both the results generated by the original code and those produced after implementing the modifications I mentioned in my previous comments. I have also uploaded the comparison results of these two files, with differences highlighted in red. The output format of the results adheres to the style of PRINT_CLIQUES_ONE_BY_ONE.

Note that I made the same modification to the findBestPivotNonNeighborsMatrix method in the TomitaAlgorithm, but it didn't affect the results. It seems that only making such modifications to the findBestPivotNonNeighborsDegeneracy method in the DegeneracyAlgorithm leads to different outcomes.

Once again, thank you for your help!

Best regards,
Joey

[darrenstrash]

Sorry for my delay @Joey199875 , I should be able to respond with a solution in the next week. For now, can you please remove your .docx attachments, and attach plaintext files? .docx files can carry viruses and in general can't be trusted. Note: There is no need to attach a highlighted files of differences, as I can run diff on the files.

[Joey199875]

No worries about the delay, I appreciate your update. I have removed the .docx attachments and attached the files in plaintext format as requested.

If you have any further instructions or requirements, please let me know.

Correct Results (without modification).txt
Incorrect Results (after modification).txt