Maximale Ähnlichkeitsgewicht-Biklik-Enumeration für große bipartite Graphen

In diesem Papier untersuchen wir das Problem der maximalen Ähnlichkeitsgewicht-Biklik-Enumeration für große bipartite Graphen. Gegeben ist ein kanten-gewichteter bipartiter Graph G = (U, \ V, \ E) und ein Gewichtsdifferenz-Schwellenwert, zielen wir darauf ab, alle maximalen Ähnlichkeitsgewicht-Bikliques in G effizient zu enumerieren, wobei ein maximaler Ähnlichkeitsgewicht-Biklik ein maximaler vollständiger Teilgraph B (L, \ R) von G ist, bei dem die Gewichtsdifferenz der Kanten in E (B) nicht größer ist als. Dieses Problem hat viele Anwendungen, wie z.B. Artikelempfehlung, Betrugserkennung und Biklustern von Genexpressionsdaten, usw. Nach unserem Wissen sind wir die ersten, die dieses Problem systematisch untersuchen. Es ist sehr herausfordernd, dieses Problem effizient zu lösen, aufgrund seiner #P-Vollständigkeit. In diesem Papier schlagen wir eine zweiphasige Branch-and-Bound-Basismethode vor, nämlich MSWBE, die den Suchraum in einer Tiefensuche-Methodik erkundet. Obwohl MSWBE ein nützliches Berechnungsframework für unser Problem bietet, ist seine Leistung aufgrund der großen Kandidatensätze während der Enumeration noch nicht zufriedenstellend. Um dies zu mindern, schlagen wir einen fortgeschrittenen Ansatz namens MSWBE++ vor. Insbesondere nutzt MSWBE++ den Suchraum, indem es die Kantenverbindung und Gewichtsinformationen gleichzeitig verwendet, und verfeinert somit den Kandidatensatz erheblich. Da wir feststellen, dass eine direkte Implementierung von MSWBE++ durch Befolgung einer Tiefensuchstrategie nicht-maximale Bikliks erzeugen kann, entwickeln wir eine Breitensuche-Strategie, um MSWBE++ zu realisieren, die nicht-maximale Mengen bereits frühzeitig ausschließen kann. Um die Berechnung zu beschleunigen, führen wir effektive Graphreduzierungstechniken ein. Unsere umfangreichen experimentellen Ergebnisse zu 10 realen Datensätzen zeigen, dass MSWBE++ die Basismethoden um bis zu 2 Magnituden übertrifft. Wir führen eine Fallstudie durch, um zu zeigen, dass maximale Ähnlichkeitsgewicht-Bikliques nützliche Suchhinweise für die Erkennung betrügerischer Bewertungen liefern können.