PROJECT TITLE :

A Stochastic Approach to Finding Densest Temporal Subgraphs in Dynamic Graphs

ABSTRACT:

Finding the densest lasting -subgraphs in large dynamic graphs, which takes into consideration the time duration of the subgraph pattern, is an important problem that has not received enough attention from researchers. A novel stochastic approach that nontrivially extends the traditional EM approach is what we refer to as the Expectation-Maximization with Utility functions (EMU) framework that we propose. The EMU has the capability of improving the performance of any user-defined utility functions. In order to validate our EMU approach, we first demonstrated that it converges to the optimal solution. Specifically, we demonstrated that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. In order to solve the problem of finding the densest lasting subgraph, we develop EMU algorithms, as well as several variants of these algorithms by modifying the utility function. We evaluate the usefulness and efficiency of our methods by analyzing data from the real world, and we contrast these results with those obtained from two earlier methods of dense subgraph detection.