International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 9, No. 4, 8 Apr. 2017
Cover page and Table of Contents: PDF (size: 942KB)
Mining Maximal Quasi Regular Patterns in Weighted Dynamic Networks
Full Text (PDF, 942KB), PP.48-62
Views: 0 Downloads: 0
Author(s)
Hardeo Kumar Thakur
1,*
Anand Gupta
1
Bhavuk Jain
2
Ambika
2
Index Terms
Dynamic weighted graph, evolving graph, regular graph, quasi regular graph, frequent graph
Abstract
Interactions appearing regularly in a network may be disturbed due to the presence of noise or random occurrence of events at some timestamps. Ignoring them may devoid us from having better understanding of the networks under consideration. Therefore, to solve this problem, researchers have attempted to find quasi/quasi-regular patterns in non-weighted dynamic networks. To the best of our knowledge, no work has been reported in mining such patterns in weighted dynamic networks. So, in this paper we present a novel method which mines maximal quasi regular patterns on structure (MQRPS) and maximal quasi regular patterns on weight (MQRPW) in weighted dynamic networks. Also, we have provided a relationship between MQRPW and MQRPS which facilitates in the running of the proposed method only once, even when both are required and thus leading to reduction in computation time. Further, the analysis of the patterns so obtained is done to gain a better insight into their nature using four parameters, viz. modularity, cliques, most commonly used centrality measures and intersection. Experiments on Enron-email and a synthetic dataset show that the proposed method with relationship and analysis is potentially useful to extract previously unknown vital information.
Cite This Paper
Hardeo Kumar Thakur, Anand Gupta, Bhavuk Jain, Ambika, "Mining Maximal Quasi Regular Patterns in Weighted Dynamic Networks", International Journal of Information Technology and Computer Science(IJITCS), Vol.9, No.4, pp.48-62, 2017. DOI:10.5815/ijitcs.2017.04.07
Reference
[1]Manjeet Samoliya, Akhilesh Tiwari, “On the use of Rough Set Theory for Mining Periodic Frequent Patterns”, International Journal of Information Technology and Computer Sciences (IJITCS), Vol. 8, No. 7, pp.53-60, 2016. DOI: 10.5815/ijitcs.2016.07.08
[2]P. K. Desikan and J. Srivastava, “Mining Temporally Changing Web Usage Graphs”, In Proc. of the 6th International Workshop on Knowledge Discovery on the Web (WEBKDD’04), 2004, pp. 1-17.
[3]K. M. Borgwardt, H. P. Kriegel, and P. Wackersreuther, “Pattern Mining in Frequent Dynamic subgraphs”, In Proc. of the 6th International Conference on Data Mining (ICDM '06) , 2006, pp. 818-822.
[4]M.Lahiri, Y. Tanya and B.Wolf , “Mining Periodic Behavior in Dynamic Social Networks”, In Proc. of the 8th IEEE International Conference on Data Mining(ICDM’08), 2008, pp.373-382.
[5]C. Robardet, “Constraint-based Pattern Mining in Dynamic Graphs”, In Proc. of the 9th IEEE International Conference on Data Mining(ICDM’09), 2009, pp. 950-955.
[6]C.H.You, L.B.Holder and D.J.Cook, “Learning patterns in the dynamics of biological networks”, In Proc. of the 15th International Conference on Knowledge Discovery and Data Mining (KDD’09), 2009, pp. 977-986 .
[7]G.Qin, L.Gao,J.Yang and J.Li “Evolution Pattern Discovery in Dynamic Networks”, In proc. of the International conference on signal Processing , Communication and Computing(ICSPCC 2011) 2011, pp.933-938.
[8]Y. Yang, J. X. Yu, H. Gao, J. Pei and J. Li, “Mining most frequently changing component in evolving graphs”, In Journal of World Wide Web, Volume 17 Issue 3, PP. 351-376, May 2014.
[9]R. Jin, S. McCallen, and E. Almaas, “Trend Motif: A Graph Mining Approach for Analysis of Dynamic Complex Networks”, In Proc. of the 7th International Conference on Data Mining (ICDM ‘07), 2007, pp. 541-546.
[10]F. Moser, R. Colak, A. Rafiey and M. Ester, “Mining Cohesive Patterns from Graphs with Feature Vectors”, In Proc. of the International Conference on Data Mining (SDM ’09), 2009, PP. 593-604.
[11]Y. Zhou, H. Cheng, and J. X. Yu, “Graph Clustering Based on Structural/Attribute Similarities”, In Journal of the VLDB Endowment, Volume 2 Issue 1, PP. 718-729, August 2009.
[12]P. Bogdanov, M. Mongiovi and A. Singh, “Mining Heavy Subgraphs in Time-Evolving Networks” In Proc. of the International Conference on Data Mining (IEEE ICDM 2011), 2011, pp. 81-90.
[13]A. Prado, M. Plantevit, C. Robardet and J. Boulicaut, “Mining Graph Topological Patterns: Finding Co ariations among Vertex Descriptors”, In Journal of the IEEE Trans. Knowl. Data Eng., Volume 25, Number 1, pp. 2090 - 2104 January 2013.
[14]A. Gupta, H. K. Thakur and P. Kishore, “Mining Regular Patterns In Weighted Directed Networks”, In Proc. of 13th International Conference Of Information Technology (ICIT ‘14), 2014, pp. 215-220.
[15]A. Gupta and H. K. Thakur., “A novel method to determine regular pattern in edge labelled dynamic graphs,” In Proc. of 7th International Conference on Data Mining and Warehousing, (ICDMW ’13), 2013, PP. 39-47.
[16]P. Pons and M. Latapy, “Computing Communities in Large Networks Using Random Walks”, In Journal of Graph Algorithms and Applications, Volume 10, Number 2, PP. 191-218 , 2006.
[17]D. Eppstein, M. Loffler, and D. Strash, “Listing all maximal cliques in sparse graphs in near-optimal time”, In Proc. Of 21st International Symposium on Algorithms and Computation (ISAAC '10), 2010, PP. 403-414.
[18]R. D. Luce and A. D. Perry, “A method of matrix analysis of group structure”, In Journal of Psychometrika, Volume 14, issue , PP. 95-116, 1949.
[19]L. C. Freeman, “Centrality in Social Networks Conceptual Clarification”, In Journal of Social Networks, Volume 1, issue 3, PP. 215-239, 1979.
[20]U. Brandes, “A Faster Algorithm for Betweenness Centrality”, In The Journal of Mathematical Sociology, Volume 25, issue 2, PP. 163-177, 2001.
[21]P. Bonacich, “Power and Centrality: A Family of Measures”, In American Journal of Sociology, Volume 92, issue 5, PP. 1170-1182, 1987.
[22]L. Tang, H. Liu, J. Zhang and Z. Nazeri, “Community Evolution in Dynamic Multi-Mode Networks”, In Proc. of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, 2008, PP.677-685.
[23]A. Clauset, M. E. J. Newman and C. Moore, “Finding community structure in very large networks”, In Journal Physical Review E, Vol. 70, Number 6. Aug. 2004.