Springer Proceedings in Mathematics & Statistics Ilya Bychkov Valery A. Kalyagin Panos M. Pardalos Oleg Prokopyev   Editors Network Algorithms, Data Mining, and Applications NET, Moscow, Russia, May 2018 Springer Proceedings in Mathematics & Statistics Volume 315 Springer Proceedings in Mathematics & Statistics This book series features volumes composed of selected contributions from workshops and conferences in all areas of current research in mathematics and statistics, including operation research and optimization. In addition to an overall evaluation of the interest, scientific quality, and timeliness of each proposal at the hands of the publisher, individual contributions are all refereed to the high quality standards of leading journals in the field. Thus, this series provides the research community with well-edited, authoritative reports on developments in the most exciting areas of mathematical and statistical research today. More information about this series at http://www.springer.com/series/10533 Ilya Bychkov Valery A. Kalyagin (cid:129) (cid:129) Panos M. Pardalos Oleg Prokopyev (cid:129) Editors Network Algorithms, Data Mining, and Applications NET, Moscow, Russia, May 2018 123 Editors Ilya Bychkov Valery A.Kalyagin Higher Schoolof Economics Higher Schoolof Economics National Research University National Research University Nizhny Novgorod,Russia Nizhny Novgorod,Russia PanosM. Pardalos OlegProkopyev Department ofIndustrial andSystems Department ofIndustrial Engineering Engineering University of Pittsburgh University of Florida Pittsburgh, PA,USA Gainesville, FL,USA ISSN 2194-1009 ISSN 2194-1017 (electronic) SpringerProceedings in Mathematics& Statistics ISBN978-3-030-37156-2 ISBN978-3-030-37157-9 (eBook) https://doi.org/10.1007/978-3-030-37157-9 Mathematics Subject Classification (2010): 05C82, 90B10, 90B15, 90-02, 90C31, 90C27, 90C09, 90C10,90C11,90C35,90B06,90B18,90B40,68R01 ©SpringerNatureSwitzerlandAG2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained hereinorforanyerrorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregard tojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface Thisvolumeisbasedonthepaperspresentedatthe8thInternationalConferenceon Network Analysis held in Moscow, Yandex office, Russia, May 18–19, 2018. The main focus of the conference and this volume is centered around the development of new network algorithms as well as underlying analysis and optimization of network structures generated by complex networks. Various applications to net- work data mining and social networks are also considered. The previous books basedonthepaperspresentedatthe1st–7thInternationalConferencesonNetwork Analysis can be found in [1–7]. The current volume consists of three major parts, namely, Network Algorithms, Network Data Mining, and Network Applications, which we briefly overview next. The first part of the book is focused on network algorithms. The chapter “Fairness in Resource Allocation: Foundation and Applications” presents a com- prehensive review offairness in resource allocation and its foundation including a complex network analysis. Fairness is applied when the resources divided on multiple demands are limited. Implementing fairness in resource allocation is a challengingtasksincefairnessandefficiencyarecontradictingobjectives.Hence,a variety of approaches from the literature are discussed in this paper. In the chapter “Mixed Integer Programming for Searching Maximum Quasi- Bicliques”, the problemoffinding themaximal quasi-bicliques in a bipartite graph (bigraph) is considered. Several models of mixed-integer programming (MIP) to search for a quasi-biclique are constructed and tested for working efficiency. In the chapter “Graph Clustering Via Intra-Cluster Density Maximization”, the clustering problem is formulated as a combinatorial optimization problem. The main contribution is a novel problem formulation that maximizes intra-cluster density, a statistically meaningful quantity, which is designed to prevent common degeneracies, like “mega clusters”. Some numerical solution techniques are presented. In the chapter “Computational Complexity of SRIC and LRIC Indices”, the computational complexity of short-range and long-range interaction centrality (SRIC and LRIC) is investigated. Several modes are proposed to decrease the v vi Preface computationalcomplexityoftheindices.Theruntimecomparisonofthesequential and parallel computation of the proposed models is also given. The chapter “A Survey on Variable Neighborhood Search Methods for Supply Network Inventory” focuses on reverse logistics and closed-loop supply chain networks that have gained substantial interest in business and academia. The dynamic lot-sizing problem with product returns and recovery are reviewed and recent successful applications of Variable Neighborhood Search (VNS) for the efficient solution of such problems are presented. The second part of the book presents several network data mining techniques. Chapter “GSM: Inductive Learning on Dynamic Graph Embeddings” studies the problem of learning graph embeddings for dynamic networks and the ability to generalize to unseen nodes called inductive learning. An improved model GSM based on GraphSAGE algorithm is introduced and the experiments on datasets CORA, Reddit, and HSEcite are conducted. The results show a good performance of the new model. Inthechapter“CollaboratorRecommenderSystem”,arecommendersystemfor the scientists from the National Research University Higher School of Economics to help them find coauthors for their future work is designed and investigated. The chapter “Visual Product Recommendation Using Neural Aggregation Network and Context Gating” focuses on the problem of user interests’ classifi- cation in visual product recommender systems. A new two-stage procedure is proposed.It isshownthat this procedurecancapturetherelationships between the product images purchased by the same user. Experiments on the Amazon product dataset confirm a good performance of the procedure. In the chapter “Network Structure and Scheme Analysis of the Russian Language Segment of Wikipedia”, a network of the Russian-language segment of Wikipedia is created and an analysis of its structure is conducted. In the chapter “Indirect Influence Assessment in the Context of Retail Food Network”,anapplicationoflong-rangeinteractioncentrality(LRIC)totheproblem of the influence assessment in the global retail food network is considered where node-to-node influence is transformed into the influence index. The model is appliedtothe foodtrade networkbased ontheWorld InternationalTrade Solution database. Thechapter“FacialClusteringinVideoDataUsingDeepConvolutionalNeural Networks” presents an automatic system that structures information in video surveillancesystemsbased ontheanalysisoffacialimages. The cluster analysisin video data using face detection in each video frame and feature extraction with pre-trained deep convolutional neural networks is suggested. Different aggregation techniques to combine frame features into a single video descriptor are imple- mented to organize video data based on clustering techniques. An experimental study with YouTube Faces dataset shows high efficiency of the model. Preface vii The third part ofthebook ison applicationsofnetworkanalysis. Inthechapter “The Existence and Uniqueness Theorem for Initial-Boundary Value Problem oftheSameClassofIntegro-DifferentialPDEs”,thesecondinitial-boundaryvalue problemforaclassofnonlinearPDEsofthesecondorderandanintegraloperator of a given form is considered. The existence and uniqueness theorem of the cor- responding initial-boundary value problem is proved. In the chapter “Mapping of Politically Active Groups on Social Networks of Russian Regions (On the Example of Karachay-Cherkessia Republic)”, social and political activity in online social networks are investigated. Clusters of political activity in social networks of some Russian regions are obtained by the author’s method of seed clustering, each cluster being analyzed by network methods. Inthe chapter“Social Mechanisms oftheSubject Area Formation. The Case of “Digital Economy””, a wide range of texts about digital economy was analyzed, making it possible to show the thematic structure of this subject area. Central and peripheral concepts were identified to characterize theoretical core concepts and related topics clarifying the application of digital economy. In the chapter “Methodology for Measuring Polarization of Political Discourse: CaseofComparingOppositionalandPatrioticDiscourseinOnlineSocialNetworks”, speech markers and semantic concepts typical for patriotic and oppositional dis- course in social networks are analyzed. An alternative method to tf–idf metric for specific text markers identification is proposed. The features of oppositional dis- course in comparison with the patriotic discourse were formulated. Inthechapter“NetworkAnalysisMethodologyofPolicyActorsIdentificationand Power Evaluation (The Case of the Unified State Exam Introduction in Russia)”, a new methodology for identifying policy actors for policy fields is proposed and investigated. The presented methodology is based on text parsing and mining and producingnetworkswithanalysisofthetextprocessingresults.Theexampleofthe RussianUnifiedStateExamisdevelopedastherealcaseofpolicyformulationand implementation. The methodology was shown tohave great potential for verifying the theories of policy studies and for a broader application in the areas where analysis of policy actors and their power, influence, and impact is needed. We would like to take this opportunity to thank all the authors and referees for their efforts. This work is supported by the Laboratory of Algorithms and TechnologiesforNetworkAnalysis(LATNA)oftheNationalResearchUniversity Higher School of Economics. Nizhny Novgorod, Russia Ilya Bychkov Nizhny Novgorod, Russia Valery A. Kalyagin Gainesville, FL, USA Panos M. Pardalos Pittsburgh, PA, USA Oleg Prokopyev viii Preface References 1. Goldengorin,B.I.,Kalyagin,V.A.,Pardalos,P.M.(eds.):Models,algorithmsandtechnologies for network analysis. In: Proceedings of the First International Conference on Network Analysis.SpringerProceedingsinMathematicsandStatistics,vol.32.Springer,Cham(2013) 2. Goldengorin,B.I.,Kalyagin,V.A.,Pardalos,P.M.(eds.):Models,algorithmsandtechnologies for network analysis. In: Proceedings of the Second International Conference on Network Analysis.SpringerProceedingsinMathematicsandStatistics,vol.59.Springer,Cham(2013) 3. Batsyn,M.V.,Kalyagin,V.A.,Pardalos,P.M.(eds.):Models,algorithmsandtechnologiesfor network analysis. In: Proceedings of Third International Conference on Network Analysis. SpringerProceedingsinMathematicsandStatistics,vol.104.Springer,Cham(2014) 4. Kalyagin, V.A., Pardalos, P.M., Rassias, T.M. (eds.): Network models in economics and finance.In:SpringerOptimizationandItsApplications,vol.100.Springer,Cham(2014) 5. Kalyagin,V.A.,Koldanov,P.A.,Pardalos,P.M.(eds.):Models,algorithmsandtechnologies for network analysis. In: NET 2014, Nizhny Novgorod, Russia, May 2014. Springer ProceedingsinMathematicsandStatistics,vol.156.Springer,Cham(2016) 6. Kalyagin, V.A., Nikolaev, A.I., Pardalos, P.M., Prokopyev, O.A. (eds.): Models, algorithms andtechnologiesfornetworkanalysis.In:NET2016,NizhnyNovgorod,Russia,May2016. SpringerProceedingsinMathematicsandStatistics,vol.197.Springer,Cham(2017) 7. Kalyagin V.A., Pardalos, P.M., Prokopyev, O.A., Utkina I.E. (eds.): Computational aspects andapplicationsinlarge-scalenetworks.In:SpringerProceedingsinMathematics&Statistics, vol.247.SpringerInternationalPublishingAG,partofSpringerNature(2018) Contents Network Algorithms Fairness in Resource Allocation: Foundation and Applications . . . . . . . 3 Hamoud S. Bin-Obaid and Theodore B. Trafalis Mixed Integer Programming for Searching Maximum Quasi-Bicliques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Dmitry I. Ignatov, Polina Ivanova and Albina Zamaletdinova Graph Clustering Via Intra-Cluster Density Maximization . . . . . . . . . . 37 Pierre Miasnikof, Leonidas Pitsoulis, Anthony J. Bonner, Yuri Lawryshyn and Panos M. Pardalos Computational Complexity of SRIC and LRIC Indices . . . . . . . . . . . . . 49 Sergey Shvydun A Survey on Variable Neighborhood Search Methods for Supply Network Inventory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Angelo Sifaleras and Ioannis Konstantaras Network Data Mining GSM: Inductive Learning on Dynamic Graph Embeddings. . . . . . . . . . 85 Marina Ananyeva, Ilya Makarov and Mikhail Pendiukhov Collaborator Recommender System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Anna Averchenkova, Alina Akhmetzyanova, Konstantin Sudarikov, Stanislav Petrov, Ilya Makarov, Mikhail Pendiukhov and Leonid E. Zhukov Visual Product Recommendation Using Neural Aggregation Network and Context Gating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Kirill V. Demochkin and Andrey V. Savchenko ix