Abstract
We discuss in this paper a problem of mining structural change patterns. Given a pair of graphs before and after some change, a structural change pattern is extracted as a vertex set X which is pseudo-independent set before the change but a pseudo-clique after the change. In order to detect this kind of patterns more interesting, X is particularly required to have many outgoing edges from X before the change, while to have few outgoing edges after the change. We formalize such an X as a maximal k-plex in the combined graph defined from the given graphs. An effective algorithm for extracting them is designed as a constrained maximal k-plex enumerator with a pruning mechanism based on right candidate control. Our experimental results show an example of structural change pattern actually detected. Moreover, it is shown that the pruning mechanism and the use of combined graph are very effective for efficient computation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bay, S.D., Pazzani, M.J.: Detecting Group Differences: Mining Contrast Sets. Data Mining and Knowledge Discovery 5(3), 213–246 (2001)
Newman, M.E.J.: Finding Community Structure in Networks Using the Eigenvectors of Matrices. Phys. Rev. E 74(3), 036104 (2006)
Uno, T.: An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem. Algorithmica 56, 3–16 (2010)
Brunato, M., Hoos, H.H., Battiti, R.: On Effectively Finding Maximal Quasi-cliques in Graphs. In: Maniezzo, V., Battiti, R., Watson, J.-P. (eds.) LION 2007 II. LNCS (LNAI), vol. 5313, pp. 41–55. Springer, Heidelberg (2008)
Dong, G., Li, J.: Mining Border Descriptions of Emerging Patterns from Dataset Pairs. Knowledge and Info. Systems 8(2), 178–202 (2005)
Terlecki, P., Walczak, K.: Efficient Discovery of Top-K Minimal Jumping Emerging Patterns. In: Chan, C.-C., Grzymala-Busse, J.W., Ziarko, W.P. (eds.) RSCTC 2008. LNCS (LNAI), vol. 5306, pp. 438–447. Springer, Heidelberg (2008)
Ito, H. and Iwama, K.: Enumeration of Isolated Cliques and Pseudo-Cliques. ACM Transactions on Algorithms 5(4), Article 40 (2009)
Pattillo, J., Youssef, N., Butenko, S.: Clique Relaxation Models in Social Network Analysis. In: Thai, M.T., Pardalos, P.M. (eds.) Handbook of Optimization in Complex Networks: Communication and Social Networks. Springer Optimization and Its Applications, vol. 58, pp. 143–162 (2012)
Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 3rd edn. Morgan Kaufmann (2011)
Berlingerio, M., Bonchi, F., Bringmann, B., Gionis, A.: Mining Graph Evolution Rules. In: Buntine, W., Grobelnik, M., Mladenić, D., Shawe-Taylor, J. (eds.) ECML PKDD 2009, Part I. LNCS, vol. 5781, pp. 115–130. Springer, Heidelberg (2009)
Ozaki, T., Etoh, M.: Correlation and Contrast Link Formation Patterns in a Time Evolving Graph. In: Proc. of the 2011 IEEE 11th Int’l Conf. on Data Mining Workshops, ICDMW 2011, pp. 1147–1154 (2011)
Robardet, C.: Constraint-Based Pattern Mining in Dynamic Graphs. In: Proc. of the 2009 Ninth IEEE Int’l Conf. on Data Mining - ICDM 2009, pp. 950 - 955 (2009)
Li, Z., Xiong, H., Liu, Y.: Mining Blackhole and Volcano Patterns in Directed Graphs: A General Approach. In: Data Mining and Knowledge Discovery, pp. 1–26. Springer (2012)
Bron, C., Kerbosch, J.: Algorithm 457 - Finding All Cliques of an Undirected Graph. Communications of the ACM 16(9), 575–577 (1973)
Wu, B., Pei, X.: A Parallel Algorithm for Enumerating All the Maximal k-Plexes. In: Washio, T., Zhou, Z.-H., Huang, J.Z., Hu, X., Li, J., Xie, C., He, J., Zou, D., Li, K.-C., Freire, M.M. (eds.) PAKDD 2007. LNCS (LNAI), vol. 4819, pp. 476–483. Springer, Heidelberg (2007)
Taniguchi, T., Haraguchi, M.: Discovery of Hidden Correlations in a Local Transaction Database Based on Differences of Correlations. Engineering Application of Artificial Intelligence 19(4), 419–428 (2006)
Li, A., Haraguchi, M., Okubo, Y.: Top-N Minimization Approach for Indicative Correlation Change Mining. In: Perner, P. (ed.) MLDM 2012. LNCS (LNAI), vol. 7376, pp. 102–116. Springer, Heidelberg (2012)
Seidman, S.B., Foster, B.L.: A Graph Theoretic Generalization of the Clique Concept. Journal of Mathematical Sociology 6, 139–154 (1978)
Tomita, E., Tanaka, A., Takahashi, H.: The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Theoretical Computer Science 363(1), 28–42 (2006)
Eppstein, D., Strash, D.: Listing All Maximal Cliques in Large Sparse Real-World Graphs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 364–375. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okubo, Y., Haraguchi, M., Tomita, E. (2012). Structural Change Pattern Mining Based on Constrained Maximal k-Plex Search. In: Ganascia, JG., Lenca, P., Petit, JM. (eds) Discovery Science. DS 2012. Lecture Notes in Computer Science(), vol 7569. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33492-4_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-33492-4_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33491-7
Online ISBN: 978-3-642-33492-4
eBook Packages: Computer ScienceComputer Science (R0)