Important subgraph discovery using non-dominance criterion

: pp. 733–747
Received: February 18, 2023
Accepted: July 17, 2023
Faculty of Sciences Ain Chock, Hassan II University
Faculty of Sciences Ain Chock, Hassan II University
Department of Mathematics and Computer Science, Fundamental and Applied Mathematics Laboratory, Faculty of Sciences Ain Chock, Hassan II University of Casablanca, Morocco

Graph mining techniques have received a lot of attention to discover important subgraphs based on certain criteria.  These techniques have become increasingly important due to the growing number of applications that rely on graph-based data.  Some examples are: (i) microarray data analysis in bioinformatics, (ii) transportation network analysis, (iii) social network analysis.  In this study, we propose a graph decomposition algorithm using the non-dominance criterion to identify important subgraphs based on two characteristics: edge connectivity and diameter.  The proposed method uses a multi-objective optimization approach to maximize the edge connectivity and minimize the diameter.  In a similar vein, identifying communities within a network can improve our comprehension of the network's characteristics and properties.  Therefore, the detection of community structures in networks has been extensively studied.  As a result, in this paper an innovative community detection method is presented based on our approach.  The performance of the proposed technique is examined on both real-life and synthetically generated data sets.

  1. Rehman S. U., Asmat U. K., Simon F.  Graph mining: A survey of graph mining techniques.  Seventh International Conference on Digital Information Management (ICDIM 2012). 88–92 (2012).
  2. Nandita B., Anmol R G.  Graph-based data mining: A new approach for data analysis.  International Journal of Scientific & Engineering Research.  5 (5), 1230–1236 (2014).
  3. Papadias D., Tao Y., Fu G., Seeger B.  Progressive skyline computation in database systems.  ACM Transactions on Database Systems (TODS).  30 (1), 41–82 (2005).
  4. Papadopoulos A. N., Lyritsis A., Manolopoulos Y.  Skygraph: an algorithm for important subgraph discovery in relational graphs.  Data Mining and Knowledge Discovery.  17, 57–76 (2008).
  5. Hartuv E., Shamir R.  A clustering algorithm based on graph connectivity.  Information Processing Letters.  76 (4–6), 175–181 (2000).
  6. Shelokar P., Quirin A., Cordón Ó.  A multiobjective evolutionary programming framework for graph-based data mining.  Information Sciences.  237, 118–136 (2013).
  7. Shelokar P., Quirin A., Cordón Ó.  Three-objective subgraph mining using multiobjective evolutionary programming.  Journal of Computer and System Sciences.  80 (1), 16–26 (2014).
  8. Danisch M., Chan T.-H. H., Sozio M.  Large scale density-friendly graph decomposition via convex programming.  WWW '17: Proceedings of the 26th International Conference on World Wide Web. 233–242 (2017).
  9. Kong Y.-X., Shi G.-Y., Wu R.-J., Zhang Y.-C.  $k$-core: Theories and applications.  Physics Reports.  832, 1–32 (2019).
  10. Tatti N.  Density-friendly graph decomposition.  ACM Transactions on Knowledge Discovery from Data.  13 (5), 1–29 (2019).
  11. Lancichinetti A., Fortunato S.  Community detection algorithms: A comparative analysis.  Physical Review E.  80 (5), 056117 (2009).
  12. Cuvelier E., Aufaure M.-A.  Graph Mining and Communities Detection.  European Big Data Management and Analytics Summer School, eBISS 2011: Business Intelligence. 117–138 (2012).
  13. Shin H., Park J., Kang D.  A graph-cut-based approach to community detection in networks.  Applied Sciences.  12 (12), 6218 (2022).
  14. Stoer M., Wagner F.  A simple min-cut algorithm.  Journal of the ACM.  44 (4), 585–591 (1997).
  15. Nagamochi H., Ibaraki T.  Computing edge-connectivity in multigraphs and capacitated graphs.  SIAM Journal on Discrete Mathematics.  5 (1), 54–66 (1992).
Mathematical Modeling and Computing, Vol. 10, No. 3, pp. 733–747 (2023)