Top

Social Network Analysis and Mining

Published in:

01-12-2020 | Original Article

Online social network trend discovery using frequent subgraph mining

Authors: Saif Ur Rehman, Sohail Asghar

Published in: Social Network Analysis and Mining | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Graph mining has become a well-established discipline within the domain of data mining. It has received much interest over the last decade as advances in computer hardware have provided the processing power to enable large-scale graph data mining to be conducted. Frequent subgraph mining (FSM) plays a very significant role in graph mining, attracting a great deal of attention in different domains, such as Bioinformatics, web data mining and social networks. Online social networks (SNs) play an important role in today’s Internet. These social networks contain huge amounts of data and present a challenging problem. FSM has been used in SNs to identify the frequent pattern trends existing in the network. A frequent pattern trend is defined as a sequence of time-stamped occurrences (support) value for specific frequent pattern that exist in the data. For example, most active researchers, most visited web pages or users’ navigation patterns over the web are few to mention. In the past few years, social network trend mining has been an active area of research. Many graph mining algorithms have been proposed, but a very limited effort exists for capturing an important dimension of SNs, which is trends discovery. Therefore, this paper introduces a novel FSM approach, called A-RAFF (A RAnked Frequent pattern-growth Framework), to discovering and comparing the frequent pattern trends exist in the social network data. Furthermore, the social network frequent pattern trend analysis has been evaluated using two standard social networks, Facebook-like network and the famous MSNBC news network datasets. Consequently, the discovered trends will help the underlying social networks to further enhance their platforms for the betterment of the users as well as for their business growth.

previous article Identification of medical resource tweets using Majority Voting-based Ensemble during disaster

next article Analyzing the relationship between relevance and extremist discourse in an alt-right network on Twitter

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Agrebi S, Jallais J (2015) Explain the intention to use smartphones for mobile shopping. J Retail Consum Serv 22:16–23CrossRef

Algur SP, Bhat P (2016) Web video object mining: expectation maximization and density based clustering of web video metadata objects. Int J Inform Eng Electron Bus 8(1):69

Bhat SY, Abulaish M (2013) Analysis and mining of online social networks: emerging trends and challenges. Wiley Interdiscip Rev Data Min Knowl Discov 3(6):408–444CrossRef

Borgatti SP, Mehra A, Brass DJ, Labianca G (2009) Network analysis in the social sciences. Science 323(5916):892–895CrossRef

Borgelt C, Berthold MR (2002) Mining molecular fragments: finding relevant substructures of molecules. In: 2002 IEEE international conference on data mining, pp 51–58. IEEE

Boyd DM, Ellison NB (2007) Social network sites: definition, history, and scholarship. J Comput Med Commun 13(1):210–230CrossRef

Breiger RL (2004) The analysis of social networks, pp 505–526. na

Cadez I, Heckerman D, Meek C, Smyth P, White S (2000) Visualization of navigation patterns on a web site using model-based clustering. In: KDD, pp 280–284

Chen C, Yan X, Yu PS, Han J, Zhang DQ, Gu X (2007) Towards graph containment search and indexing. In: Proceedings of the 33rd international conference on very large data bases, pp 926–937. VLDB Endowment

Chen C, Lin CX, Yan X, Han J (2008) On effective presentation of graph patterns: a structural representative approach. In: Proceedings of the 17th ACM conference on information and knowledge management, pp 299–308. ACM

Cook DJ, Holder LB (eds) (2006) Mining graph data. Wiley, Hoboken

De Choudhury M, Sundaram H, John A, Seligmann DD (2008) Can blog communication dynamics be correlated with stock market activity? In: Proceedings of the nineteenth ACM conference on hypertext and hypermedia, pp 55–60. ACM

Dehaspe L, Toivonen H, King RD (1998) Finding frequent substructures in chemical compounds. In: KDD98. http://dx.doi.org/10.1.1.26.1344

Deshpande M, Kuramochi M, Wale N, Karypis G (2005) Frequent substructure-based approaches for classifying chemical compounds. IEEE Trans Knowl Data Eng 17(8):1036–1050CrossRef

Dong G, Li J (1999) Efficient mining of emerging patterns: discovering trends and differences. In: Proceedings of the fifth ACM SIGKDD international conference on knowledge discovery and data mining, pp 43–52. ACM

Eberle W, Holder L (2007) Discovering structural anomalies in graph-based data. In: Seventh IEEE international conference on data mining workshops (ICDMW 2007), pp 393–398. IEEE

Fan W, Zhang K, Cheng H, Gao J, Yan X, Han J, Verscheure O (2008) Direct mining of discriminative and essential frequent patterns via model-based search tree. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, pp 230–238. ACM

Freedman S, Jin GZ (2017) The information value of online social networks: lessons from peer-to-peer lending. Int J Ind Organ 51:185–222CrossRef

GeethaRamani R, Revathy P, Lakshmi B (2019) Aggregated clustering for grouping of users based on web page navigation behaviour. Int J Reason Based Intell Syst 11(2):161–169

Gloor PA, Krauss J, Nann S, Fischbach K, Schoder D (2009) Web science 2.0: identifying trends through semantic social network analysis. In: 2009 international conference on computational science and engineering, vol 4, pp 215–222. IEEE

Guo P, Wang XR, Kang YR (2006) Frequent mining of subgraph structures. J Exp Theor Artif Intell 18(4):513–521CrossRef

Heatherly R, Kantarcioglu M, Thuraisingham B (2012) Preventing private information inference attacks on social networks. IEEE Trans Knowl Data Eng 25(8):1849–1862CrossRef

Holder LB, Cook DJ, Djoko S (1994) Substucture discovery in the subdue system. In: KDD workshop, pp 169–180

Huan J, Wang W, Prins J (2003) Efficient mining of frequent subgraphs in the presence of isomorphism. In: Third IEEE international conference on data mining, pp 549–552. IEEE

Iqbal M, Rehman S (2016) Association rule mining using computational ıntelligence technique. Int J Comput Sci Inform Secur 14(12):416

Jalili M, Orouskhani Y, Asgari M, Alipourfard N, Perc M (2017) Link prediction in multiplex online social networks. R Soc Open Sci 4(2):160863MathSciNetCrossRef

Jameel S, Rehman S (2018) An optimal feature selection method using a modified wrapper-based ant colony optimisation. J Natl Sci Found Sri Lanka 46(2):143–151CrossRef

Keramatfar A, Amirkhani H (2019) Bibliometrics of sentiment analysis literature. J Inform Sci 45(1):3–15CrossRef

Kim J, Hastak M (2018) Social network analysis: characteristics of online social networks after a disaster. Int J Inf Manag 38(1):86–96CrossRef

Kim J, Philip SY, Memon N (2013) Social network and high performance in smart communications. J Supercomput 66(2):611–613CrossRef

Krebs VE (2002) Mapping networks of terrorist cells. Connections 24(3):43–52

Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings 2001 IEEE international conference on data mining, pp 313–320. IEEE

Kuramochi M, Karypis G (2004) An efficient algorithm for discovering frequent subgraphs. IEEE Trans Knowl Data Eng 16(9):1038–1051CrossRef

Maugey T, Ortega A, Frossard P (2015) Graph-based representation for multiview image geometry. IEEE Trans Image Process 24(5):1573–1586MathSciNetCrossRef

Mislove A, Marcon M, Gummadi KP, Druschel P, Bhattacharjee B (2007) Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM conference on internet measurement, pp 29–42. ACM

Moosavi SA, Jalali M, Misaghian N, Shamshirband S, Anisi MH (2017) Community detection in social networks using user frequent pattern mining. Knowl Inf Syst 51(1):159–186CrossRef

Nijssen S, Kok JN (2004) A quickstart in frequent structure mining can make a difference. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining, pp 647–652. ACM

Opsahl T, Panzarasa P (2009) Clustering in weighted networks. Soc Netw 31(2):155–163CrossRef

Opsahl T, Colizza V, Panzarasa P, Ramasco JJ (2008) Prominence and control: the weighted rich-club effect. Phys Rev Lett 101(16):168702CrossRef

Panda B, Tripathy SN, Sethi N, Samantray OP (2016) A comparative study on serial and parallel web content mining. Int J Adv Netw Appl 7(5):2882

Rehman S, Asghar S (2014) Performance evaluation of frequent subgraph discovery techniques. In: Mathematical problems in engineering

Rehman SU, Asghar S (2019) A-RAFF: a ranked frequent pattern-growth subgraph pattern discovery approach. J Internet Technol 20(1):257–267

Rehman SU, Asghar S, Fong S (2018) An efficient ranking scheme for frequent subgraph patterns. In: Proceedings of the 2018 10th international conference on machine learning and computing, pp 257–262

Rehman S, Asghar S, Fong S (2018b) Optimized and frequent subgraphs: how are they related? IEEE Access 6(1):37237–37249CrossRef

Riba P, Lladós J, Fornés A, Dutta A (2017) Large-scale graph indexing using binary embeddings of node contexts for information spotting in document image databases. Pattern Recogn Lett 87:203–211CrossRef

Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining, pp 61–70. ACM

Saha TK, Al Hasan M (2015) FS3: a sampling based method for top-k frequent subgraph mining. Stat Anal Data Min ASA Data Sci J 8(4):245–261CrossRef

Scott J (1988) Social network analysis. Sociology 22(1):109–127CrossRef

Serrat O (2017) Social network analysis. In: Knowledge solutions, pp 39–43. Springer, Singapore

Shahrivari S, Jalili S (2015) High-performance parallel frequent subgraph discovery. J Supercomput 71(7):2412–2432CrossRef

Somaraki V, Broadbent D, Coenen F, Harding S (2010) Finding temporal patterns in noisy longitudinal data: a study in diabetic retinopathy. In: Industrial conference on data mining, pp 418–431. Springer, Berlin, Heidelberg

Sonawane SS, Kulkarni PA (2014) Graph based representation and analysis of text document: a survey of techniques. Int J Comput Appl 96(19):1–8

Sumathi CP, Valli RP, Santhanam T (2010) Automatic recommendation of web pages in web usage mining. Int J Comput Sci Eng 2(9):3046–3052

Suresh K, Mohana RM, Reddy ARM, Subramanyam A (2011) Improved FCM algorithm for clustering on web usage mining. In: 2011 international conference on computer and management (CAMAN), pp 1–4. IEEE

Tsuda K, Kudo T (2006) Clustering graphs by weighted substructure mining. In: Proceedings of the 23rd international conference on machine learning, pp 953–960. ACM

Van Dongen SM (2000) Graph clustering by flow simulation (Doctoral dissertation)

Vascellaro JE (2007) Social networking goes professional: doctors, salesmen, executives turn to new sites to consult, commiserate with peers; weeding out impostors. Wall Street J

Wasserman S, Faust K (1994) Social network analysis: methods and applications, vol 8. Cambridge University Press, CambridgeCrossRef

Wolfe AW (1997) Social network analysis: methods and applications. Am Ethnol 24(1):219–220CrossRef

Yan X, Yu PS, Han J (2004) Graph indexing: a frequent structure-based approach. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, pp 335–346. ACM

Yan X, Zhu F, Han J, Yu PS (2006) Searching substructures with superimposed distance. In 22nd international conference on data engineering (ICDE’06), pp 88–88. IEEE

Yan X, Cheng H, Han J, Yu PS (2008) Mining significant graph patterns by leap search. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, pp 433–444. ACM

Yu LT, Chung FL, Chan SC, Yuen S (2004) Using emerging pattern based projected clustering and gene expression data for cancer detection. In: Proceedings of the second conference on Asia-Pacific bioinformatics, vol 29, pp 75–84. Australian Computer Society, Inc

Zhang S, Yang J, Jin W (2010) SAPPER: subgraph indexing and approximate matching in large graphs. Proc VLDB Endow 3(1–2):1185–1194CrossRef

Zhang X, Ouyang T, Pan D, Si X, Rahman S (2016) U.S. Patent No. 9,497,053. U.S. Patent and Trademark Office, Washington, DC

Zheng X, Zhang X, Yu Y, Kechadi T, Rong C (2016) ELM-based spammer detection in social networks. J Supercomput 72(8):2991–3005CrossRef

Zhou F, Qu Q, Toivonen H (2017) Summarisation of weighted networks. J Exp Theor Artif Intell 29(5):1023–1052CrossRef

Title: Online social network trend discovery using frequent subgraph mining
Authors: Saif Ur Rehman
Sohail Asghar
Publication date: 01-12-2020
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2020
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-020-00682-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Towards establishing the effect of self-similarity on influence maximization in online social networks

Elite versus mass polarization on the Brazilian impeachment proceedings of 2016

Accurate link prediction method based on path length between a pair of unlinked nodes and their degree

Enhancing information retrieval performance by using social analysis

GCNEXT: graph convolutional network with expanded balance theory for fraudulent user detection

Channel retrieval: finding relevant broadcasters on Telegram

Premium Partner