1
$\begingroup$

Currently, I have a dataset with pairs . The idea is to detect any anomaly in these relationships. I was able to just use pandas to do the analysis so far.

|Customer|Agent|Duration|Marks|etc
|C1..............| A1......| 2hrs.......|23 |

enter image description here

As an example above, you can project the bipartite nodes into Agent nodes. You get a normal graph then. All Agents which share a common Customer, form cliques, which you can easily get just using pandas operations in the original graph.

Other than this, is there any worthwhile algorithms to run ? Or any links will be appreciated as well.
Btw, I have good experience working with many unipartite graphs (normal), where I have run many types of algorithms (centrality measures, clique/communities, connected components etc) and social network analysis.

Edit : Just to confirm, my question is not to get the subgraph or write any new algorithms. I am just going to be using Networkx to achieve this. However, I am stuck at what are the analytics possibilities with bipartite graphs ?

Edit : I am digging through the web. And add the resources here, as I find them. Once I find something useful, I will add a solution to my question. 🤞

  1. http://www.appstate.edu/~hirsthp/talks/SocialNetworks/intro-to-graphs.pdf
  2. Networkx - Lists all bipartite graph algorithms
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The projection is also called intersection graph. There are many interesting things you can ask related to the original bipartite graph. Some examples are link prediction (if you have a time dimension) or recovering the communities, where the bipartite graph will give you the ground truth. $\endgroup$
    – Valentas
    Nov 1, 2022 at 15:07
  • $\begingroup$ hi @Valentas, What is link prediction ? Recovering the communitie ? In the projected or intersection graph, we can form cliques/communities, but what is their significance. Agents within a clique share the same customer but agents within a community share multiple customers. However, I am still not sure what kind of useful insight is this ? $\endgroup$
    – mehmat
    Nov 3, 2022 at 7:44
  • 1
    $\begingroup$ I don't know what you mean by 'useful'. The type of the dataset you have is useful for research because you can study algorithms which are given only the projected data and try to recover the original bipartite graph. If you are talking about usefulness for anomaly detection, obviously, the original dataset has more information than the projected dataset (intersection graph). In the intersection graph you see a big clique. Is it because a single big customer? Or because there is a large set of clients all connected to a large set of agents (biclique). That could be an anomaly. $\endgroup$
    – Valentas
    Nov 3, 2022 at 8:11
  • $\begingroup$ I mean there is no need to do a intersection/projection graph, to see a big customer. A pandas group-by query is enough. To put it simply, what kind of graph analytics/algorithms can be used on a bipartite graph to detect anomalous behaviour which CANNOT be simply achieved via pandas. Just thinking out aloud as I am not sure how to proceed. $\endgroup$
    – mehmat
    Nov 4, 2022 at 2:25
  • 1
    $\begingroup$ Dear mehmat. I think you are right. Just use pandas and in 99% cases it will be enough. $\endgroup$
    – Valentas
    Nov 4, 2022 at 12:04

1 Answer 1

Reset to default
2
$\begingroup$

I can see it as: you want all the edges of graph $G$ while taking the $S \subset G=(V,E)$. For your problem this $S$ is an induced subgraph and the problem you are talking about relates to induced matching, where you want a matched subgraph $M$ with every edge connecting any two vertices of $M$. It is the maximum induced matching problem you're talking about. You can check the theory of maximum subgraph matching from here. Also it is an NP-Complete problem for Bipartite graphs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi, Thanks for answering. However, my question is not to get the subgraph. Networkx has a method to do just that. My main question, is what kind of analytics approaches makes sense for bipartite grahs. $\endgroup$
    – mehmat
    Nov 1, 2022 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.