Graph Theoretic Approaches for Analyzing Large-Scale Social Networks Natarajan Meghanathan Jackson State University, USA A volume in the Advances in Wireless Technologies and Telecommunication (AWTT) Book Series Published in the United States of America by IGI Global Information Science Reference (an imprint of IGI Global) 701 E. Chocolate Avenue Hershey PA, USA 17033 Tel: 717-533-8845 Fax: 717-533-8661 E-mail: [email protected] Web site: http://www.igi-global.com Copyright © 2018 by IGI Global. All rights reserved. No part of this publication may be reproduced, stored or distributed in any form or by any means, electronic or mechanical, including photocopying, without written permission from the publisher. Product or company names used in this set are for identification purposes only. Inclusion of the names of the products or companies does not indicate a claim of ownership by IGI Global of the trademark or registered trademark. Library of Congress Cataloging-in-Publication Data Names: Meghanathan, Natarajan, 1977- editor. Title: Graph theoretic approaches for analyzing large-scale social networks / Natarajan Meghanathan, editor. Description: Hershey, PA : Information Science Reference, [2018] Identifiers: LCCN 2017010785| ISBN 9781522528142 (hardcover) | ISBN 9781522528159 (ebook) Subjects: LCSH: Social networks. | Sociometry. | Social sciences--Network analysis. | Graph theory. Classification: LCC HM741 .G73 2018 | DDC 302.3--dc23 LC record available at https://lccn.loc.gov/2017010785 This book is published in the IGI Global book series Advances in Wireless Technologies and Telecommunication (AWTT) (ISSN: 2327-3305; eISSN: 2327-3313) British Cataloguing in Publication Data A Cataloguing in Publication record for this book is available from the British Library. All work contributed to this book is new, previously-unpublished material. The views expressed in this book are those of the authors, but not necessarily of the publisher. For electronic access to this publication, please contact: [email protected]. Advances in Wireless Technologies and Telecommunication (AWTT) Book Series Xiaoge Xu The University of Nottingham Ningbo China, China ISSN:2327-3305 Mission EISSN:2327-3313 The wireless computing industry is constantly evolving, redesigning the ways in which individuals share information. Wireless technology and telecommunication remain one of the most important technolo- gies in business organizations. The utilization of these technologies has enhanced business efficiency by enabling dynamic resources in all aspects of society. The Advances in Wireless Technologies and Telecommunication Book Series aims to provide researchers and academic communities with quality research on the concepts and developments in the wireless technology fields. Developers, engineers, students, research strategists, and IT managers will find this series useful to gain insight into next generation wireless technologies and telecommunication. Coverage • Network Management IGI Global is currently accepting manuscripts • Wireless sensor networks for publication within this series. To submit a pro- • Virtual Network Operations posal for a volume in this series, please contact our • Broadcasting Acquisition Editors at [email protected] • Digital Communication or visit: http://www.igi-global.com/publish/. • Mobile Technology • Global Telecommunications • Radio Communication • Grid Communications • Wireless Technologies The Advances in Wireless Technologies and Telecommunication (AWTT) Book Series (ISSN 2327-3305) is published by IGI Global, 701 E. Chocolate Avenue, Hershey, PA 17033-1240, USA, www.igi-global.com. This series is composed of titles available for purchase individu- ally; each title is edited to be contextually exclusive from any other title within the series. For pricing and ordering information please visit http://www.igi-global.com/book-series/advances-wireless-technologies-telecommunication-awtt/73684. Postmaster: Send all address changes to above address. ©© 2018 IGI Global. All rights, including translation in other languages reserved by the publisher. No part of this series may be reproduced or used in any form or by any means – graphics, electronic, or mechanical, including photocopying, recording, taping, or information and retrieval systems – without written permission from the publisher, except for non commercial, educational use, including classroom teaching purposes. The views expressed in this series are those of the authors, but not necessarily of IGI Global. Titles in this Series For a list of additional titles in this series, please visit: www.igi-global.com/book-series Routing Protocols and Architectural Solutions for Optimal Wireless Networks and Security Dharm Singh (Namibia University of Science and Technology, Namibia) Information Science Reference • ©2017 • 277pp • H/C (ISBN: 9781522523420) • US $205.00 Sliding Mode in Intellectual Control and Communication Emerging Research and Opportunities Vardan Mkrttchian (HHH University, Australia) and Ekaterina Aleshina (Penza State University, Russia) Information Science Reference • ©2017 • 128pp • H/C (ISBN: 9781522522928) • US $140.00 Emerging Trends and Applications of the Internet of Things Petar Kocovic (Union – Nikola Tesla University, Serbia) Reinhold Behringer (Leeds Beckett University, UK) Muthu Ramachandran (Leeds Beckett University, UK) and Radomir Mihajlovic (New York Institute of Technology, USA) Information Science Reference • ©2017 • 330pp • H/C (ISBN: 9781522524373) • US $195.00 Resource Allocation in Next-Generation Broadband Wireless Access Networks Chetna Singhal (Indian Institute of Technology Kharagpur, India) and Swades De (Indian Institute of Technology Delhi, India) Information Science Reference • ©2017 • 334pp • H/C (ISBN: 9781522520238) • US $190.00 Multimedia Services and Applications in Mission Critical Communication Systems Khalid Al-Begain (University of South Wales, UK) and Ashraf Ali (The Hashemite University, Jordan & University of South Wales, UK) Information Science Reference • ©2017 • 331pp • H/C (ISBN: 9781522521136) • US $200.00 Big Data Applications in the Telecommunications Industry Ye Ouyang (Verizon Wirless, USA) and Mantian Hu (Chinese University of Hong Kong, China) Information Science Reference • ©2017 • 216pp • H/C (ISBN: 9781522517504) • US $145.00 Handbook of Research on Recent Developments in Intelligent Communication Application Siddhartha Bhattacharyya (RCC Institute of Information Technology, India) Nibaran Das (Jadavpur University, India) Debotosh Bhattacharjee (Jadavpur University, India) and Anirban Mukherjee (RCC Institute of Information Technology, India) Information Science Reference • ©2017 • 671pp • H/C (ISBN: 9781522517856) • US $360.00 701 East Chocolate Avenue, Hershey, PA 17033, USA Tel: 717-533-8845 x100 • Fax: 717-533-8661 E-Mail: [email protected] • www.igi-global.com Editorial Advisory Board MichaelR.Bartolacci,Pennsylvania State University – Berks, USA TapalinaBhattasali,University of Calcutta, India AndrasFarago,The University of Texas at Dallas, USA SrimannarayanaIyengar,VIT University Vellore, India SarojaKanchi,Kettering University, USA MohammadS.Khan,Texas A&M University – Kingsville, USA ArunKhosla,B. R. Ambedkar National Institute of Technology, India ValdisKrebs,Orgnet LLC, USA A.V.SenthilKumar,Hindusthan College of Arts and Science, India SanjayMadria,Missouri University of Science and Technology – Rolla, USA MadhumangalPal,Vidyasagar University, India MahendraPiraveenan,The University of Sydney, Australia DandaRawat,Georgia Southern University, USA YenumulaReddy,Grambling State University, USA List of Reviewers MohdVasimAhamad,Aligarh Muslim University, India NadeemAkhtar,Aligarh Muslim University, India S.RaoChintalapudi,University College of Engineering Kakinada, India AlessandroDiStefano,University of Catania, Italy BaagyereY.Edward,University of Electronic Science and Technology of China, China DimpleJuneja,YMCA University of Science and Technology, India DimitriosKatsaros,University of Thessaly – Volos, Greece MaikelY.Leyva-Vázquez,Universidad de Guayaquil, Ecuador Juan-FranciscoMartinez-Cerda,Universitat Oberta de Catalunya, Spain M.H.M.KrishnaPrasad,University College of Engineering Kakinada, India V.KamakshiPrasad,JNTU Hyderabad, India BapujiRao,Indira Gandhi Institute of Technology, India LeandrosTassiulas,Yale University, USA  Table of Contents Preface.................................................................................................................................................xvi Chapter 1 AWalkThroughSocialNetworkAnalysis:Opportunities,Limitations,andThreats...........................1 Atul Srivastava, YMCA University of Science and Technology, India Anuradha Pillai, YMCA University of Science and Technology, India Dimple Juneja Gupta, NIT Kurukshetra, India Chapter 2 GraphToolsforSocialNetworkAnalysis............................................................................................18 Nadeem Akhtar, Aligarh Muslim University, India Mohd Vasim Ahamad, Aligarh Muslim University, India Chapter 3 AnApproachtoMiningInformationFromTelephoneGraphUsingGraphMiningTechniques........34 Bapuji Rao, IGIT, India Sasmita Mishra, IGIT, India Sarojananda Mishra, IGIT, India Chapter 4 ADynamicandContext-AwareSocialNetworkApproachforMultipleCriteriaDecisionMaking ThroughaGraph-BasedKnowledgeLearning.....................................................................................53 Alessandro Di Stefano, University of Catania, Italy Marialisa Scatà, University of Catania, Italy Aurelio La Corte, University of Catania, Italy Evelina Giacchi, University of Catania, Italy Chapter 5 UndirectedBipartiteNetworksasanAlternativeMethodologytoProbabilisticExploration: OnlineInteractionandAcademicAttainmentinMOOC.....................................................................75 Juan-Francisco Martínez-Cerdá, Universitat Oberta de Catalunya (UOC), Spain Joan Torrent-Sellens, Universitat Oberta de Catalunya (UOC), Spain    Chapter 6 SocialNetworkAnalysisofDifferentParametersDerivedFromReal-TimeFacebookProfiles..........95 Paramita Dey, Government College of Engineering and Ceramic Technology, Spain Krishnendu Dutta, Government College of Engineering and Ceramic Technology, Spain Chapter 7 ContextSpecificModelingofCommunicationalandInformationalContentinFacebook...............109 Johannes Schick, University of Münster, Germany Martin Kuboschek, Informationstechnikzentrum Bund, Germany Wolfram Manfred Lippe, University of Münster, Germany Chapter 8 Hadoop-BasedDistributedK-ShellDecompositionforSocialNetworks..........................................125 Katerina Pechlivanidou, University of Thessaly, Greece Dimitrios Katsaros, University of Thessaly, Greece Leandros Tassiulas, Yale University, USA Chapter 9 ParallelizingLarge-ScaleGraphAlgorithmsUsingtheApacheSpark-DistributedMemory System................................................................................................................................................146 Ahmad Askarian, University of Texas at Dallas, USA Rupei Xu, University of Texas at Dallas, USA Andras Farago, University of Texas at Dallas, USA Chapter 10 LinkPredictioninSocialNetworks....................................................................................................164 Sovan Samanta, Tamralipta Mahavidyalaya, India Madhumangal Pal, Vidyasagar University, India Chapter 11 VisualizingCo-AuthorshipSocialNetworksandCollaborationRecommendationsWithCNARe...173 Michele A. Brandão, Universidade Federal de Minas Gerais, Brazil Matheus A. Diniz, Universidade Federal de Minas Gerais, Brazil Guilherme A. de Sousa, Universidade Federal de Minas Gerais, Brazil Mirella M. Moro, Universidade Federal de Minas Gerais, Brazil Chapter 12 CommunityDetectioninLarge-ScaleSocialNetworks:ASurvey....................................................189 S Rao Chintalapudi, Jawaharlal Nehru Technological University, Kakinada (JNTU-K), India M. H. M. Krishna Prasad, Jawaharlal Nehru Technological University, Kakinada (JNTU-K), India  Chapter 13 SpreadingActivationConnectivityBasedApproachtoNetworkClustering.....................................207 Alexander Troussov, The Russian Presidential Academy of National Economy and Public Administration, Russia Sergey Maruev, The Russian Presidential Academy of National Economy and Public Administration, Russia Sergey Vinogradov, The Russian Presidential Academy of National Economy and Public Administration, Russia Mikhail Zhizhin, Colorado University of Boulder, USA Chapter 14 ScalableMethodforInformationSpreadControlinSocialNetworks...............................................220 Michal Wojtasiewicz, Polish Academy of Sciences, Poland Mieczysław Kłopotek, Polish Academy of Sciences, Poland Chapter 15 TheEternal-ReturnModelofHumanMobilityandItsImpactonInformationFlow........................241 Martine Collard, University of the French West Indies, France Philippe Collard, University of Nice – Sophia Antipolis, France Erick Stattner, University of the French West Indies, France Chapter 16 TowardsaUnifiedSemanticModelforOnlineSocialNetworkstoEnsureInteroperabilityand AggregationforAnalysis....................................................................................................................267 Asmae El Kassiri, Mohammed V University, Morocco Fatima-Zahra Belouadha, Mohammed V University, Morocco Chapter 17 CanWeTrusttheHealthInformationWeFindOnline?IdentificationofInfluentialNodes.............293 Leila Weitzel, Universidade Federal Fluminense, Brazil Paulo Quaresma, Universidade de Evora, Brazil Jose Palazzo Moreira de Oliveira, Universidade Federal do Rio Grande do Sul, Brazil Danilo Artigas, Universidade Federal Fluminense, Brazil Compilation of References...............................................................................................................314 About the Contributors....................................................................................................................344 Index...................................................................................................................................................353 Detailed Table of Contents Preface.................................................................................................................................................xvi Chapter 1 AWalkThroughSocialNetworkAnalysis:Opportunities,Limitations,andThreats...........................1 Atul Srivastava, YMCA University of Science and Technology, India Anuradha Pillai, YMCA University of Science and Technology, India Dimple Juneja Gupta, NIT Kurukshetra, India Sincelastmorethanfortyyears,socialnetworkanalysis(SNA)techniqueshaveevolvedasoneofthe successfulapplicationsofInternet.Numerousreasonsdemandbetterunderstandingofthestructure ofsocialnetworks,needoftheiranalysisandtheirimpactonfutureInternetandsociety.Forinstance, findingthesharedinterestandtrustcouldbeoneofthereasonstostudysocialnetworks.Moreover,ifin future,distributedonlinesocialnetworksarepopularandbandwidthintensive,theycanhaveasignificant impactonInternettraffic,justascurrentpeer-to-peercontentdistributionnetworksdo.Regardlessof one’sstanceonthesephenomena,abetterunderstandingofthestructureofsocialnetworksislikelyto improveourunderstandingoftheopportunities,limitationsandthreatsassociatedwiththeseideas.For instance,giganticsizeofonlinesocialnetworks,theirdynamicbehavior,clusteringandprivacypolicies heldbyusersaresomeofthemajorchallenges.Thischapterpresentsanengravedreviewspanningfrom needofSNAtotheimplicationsassociatedwithit. Chapter 2 GraphToolsforSocialNetworkAnalysis............................................................................................18 Nadeem Akhtar, Aligarh Muslim University, India Mohd Vasim Ahamad, Aligarh Muslim University, India Asocialnetworkcanbedefinedasacomplexgraph,whichisacollectionofnodesconnectedviaedges. Nodesrepresentindividualactorsorpeopleinthenetwork,whereasedgesdefinerelationshipsamong thoseactors.MostpopularsocialnetworksareFacebook,Twitter,andGoogle+.Toanalyzethese socialnetworks,oneneedsspecializedtoolsforanalysis.Thischapterpresentsacomparativestudy ofsuchtoolsbasedonthegeneralgraphaspectsaswellasthesocialnetworkminingaspects.While consideringthegeneralgraphaspects,thischapterpresentsacomparativestudyoffoursocialnetwork analysistools—NetworkX,Gephi,Pajek,andIGraph—basedontheplatform,executiontime,graph types,algorithmcomplexity,inputfileformat,andgraphfeatures.Onthebasisofthesocialnetwork miningaspects,thechapterprovidesacomparativestudyonfivespecializedtools—Weka,NetMiner4, RapidMiner,KNIME,andR—withrespecttothesupportedminingtasks,mainfunctionality,acceptable inputformats,outputformats,andplatformused.