A Guide To Selecting A Network Similarity Method
A Guide to Selecting a Network Similarity Method Sucheta SoundarajanRutgers Universitys.soundarajan@cs.rutgers.eduTina Eliassi-RadRutgers Universityeliassi@cs.rutgers.eduBrian GallagherLawrence Livermore Laboratorybgallagher@llnl.govAbstractone network may be applied to a di erent network [8].We consider the problem of determining how similar two A network-similarity method might compare two netnetworks (without known node-correspondences) are. This works based on simple features such as edge density,problem occurs frequently in real-world applications such or might examine more complex (and computationallyas transfer learning and change detection. Many network- burdensome) patterns such as communities.We consider 20 network-similarity methods appliedsimilarity methods exist; and it is unclear how one shouldtoavariety of networks from diverse domains. Weselect from amongst them. We provide the first empiriconsiderthe task of network-similarity ranking, in whichcal study on the relationships between di erent networkoneisgivena reference network G as well as a set ofsimilarity methods. Specifically, we present (1) an approachothernetworks,and must rank those other networksfor identifying groups of comparable network-similarityinorderoftheirsimilarity to G. Within the contextmethods and (2) an approach for computing the consenoftherankingapplication,we present an approach tosus among a given set of network-similarity methods. Weidentifycorrelationsbetweensimilarity methods, clustercompare and contrast twenty network-similarity methods bymethods,andselectaconsensus(or median) rankingapplying our approaches to a variety of real datasets spanfromagroupofrankings.ning multiple domains. Our experiments demonstrate thatOur experiments are two-pronged. First, we ap(1) di erent network-similarity methods are surprisingly wellplyourapproaches to a set of cross-sectional datasets,correlated, (2) some complex network-similarity methodsdemonstratingseveral valuable results. (1) We showcan be closely approximated by a much simpler method, andthatthevarioussimilarity methods, although seemingly(3) a few network similarity methods produce rankings thatdi erent,producewell-correlated rankings. (2) We obare very close to the consensus ranking.serve that some complex methods can be approximatedby a much simpler method. For example, a method1 Introductionthat compares random walks from two networks is wellHow similar are two networks assuming we havecorrelated with a method that simply measures density.no known node-correspondences between them? We(3) We show that two methods – namely, NetSimile [6]study a variety of network-similarity methods in crossand Random Walk with Restarts – are consistently closesectional and longitudinal settings, and address theto the consensus. Second, we apply our approaches to afollowing questions: (1) How correlated are di erentset of longitudinal datasets. We consider three datasets,network-similarity methods to each other? (2) How caneach containing multiple networks aggregated on a dailyone automatically find groups of methods that behaveor monthly basis. Our analysis of these networks revealscomparably? (3) How can one select a single consensuscomplexities in measuring network similarity over time.method from a group of network-similarity methods?We discuss topics such as selecting an appropriate timeThe study of networked data covers diverse domainsgranularity for longitudinal data. When an appropriatefrom social sciences to physics to biology to informationtime granularity is used, we again observe high correlatechnology. While di erent networks can share importions between di erent network similarity methods.tant features, the extent of these similarities is not clear.The major contributions of our paper can beA network-similarity method is useful for applicationssummarized as follows:such as detecting when the structure of a network haschanged; or for determining when a classifier trained on We categorize network-similarity methods and introduce novel approaches for comparing them. This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratoryunder Contract DE-AC52-07NA27344; and funded in part by NSFCNS-1314603 and DTRA HDTRA1-10-1-0120. We conduct the first large-scale empirical studyof network-similarity methods. Our experimentsdemonstrate the following: (1) Di erent methods
are surprisingly well correlated. (2) Some complexmethods are closely approximated by much simplermethods. (3) A few methods produce similarityrankings that are close to the consensus ranking.of these structures, they calculate a feature vector describing its structural properties (e.g., the number ofedges within a node neighborhood); and label these feature vectors with the name of their respective network.Then, using cross-validation, they determine whether We provide practical guidance in the selection ofan SVM can accurately distinguish between the featurean appropriate network similarity method.vectors from network G1 and the feature vectors fromThe rest of the paper is organized as follows. We network G2 . In each round of cross-validation, the testprovide some background next. Sections 3 and 4 present set contains feature vectors from G1 and G2 ; and so forour categorization of network-similarity methods and each of G1 and G2 , they create a length-2 feature vecour comparison approaches. These are followed by tor (respectively, F1 and F2 ) describing the fraction ofour experiments and discussion in Sections 5 and 6, feature vectors from that network that were classifiedas belonging to G1 and the fraction that were classifiedrespectively. We conclude the paper in Section 7.as belonging to G2 . They define the similarity betweenG1 and G2 as 1 Canberra(F1 , F2 ). If G1 and G2 have2 BackgroundQuantifying the di erence between two networks is crit- very similar local structure, then we expect that SVMical in applications such as transfer learning and change will not be able to distinguish between the two classesdetection. A variety of network-similarity methods have of feature vectors, and F1 and F2 will be very similar.been proposed for this task (see Section 3 for details). The distance between F1 and F2 will be very low, andThe roots of this problem can be traced to the prob- so the similarity will be high. Conversely, if G1 and G2lem of determining graph isomorphism, for which no have very di erent structures, then the SVM will haveknown polynomial-time algorithm exists. The network- high classification accuracy, and a low similarity score.Matching-based methods use the same structuressimilarity task is much more general. For example,andfeature vectors obtained in the classifier-basedtwo networks can be similar without being isomorphic.methods.However, instead of using a classifier toThere are many network-similarity algorithms that redistinguishbetweenthe two classes, they match featurequire known node-correspondences (e.g., DeltaCon [12]vectorsfromGwithsimilar feature vectors from G2 ;1and most edit-distance based methods). Others do notandcalculatethecostof this matching. Specifically,require known node-correspondence (e.g., NetSimile [6]theycreateacompletebipartitegraph in which nodes inand graphlet-based approaches [16]).the first part correspond to feature vectors from G1 andnodes in the second part correspond to feature vectors3 Network Similarity Methodsfrom G2 . The weight of an edge in this bipartite graphWe categorize a network-similarity method based onis the Canberra distance between the correspondingtwo criteria. First, at what level of the network doesfeature vectors. They then find a least-cost matching onit operate? Second, what type of comparison does itthis bipartite graph, and the similarity is 1 minus theuse? For the first criterion, we define 3 levels: micro,average cost of edges in the matching. If every featuremezzo, and macro. As their names suggest, at thevector in G1 has an equal feature vector in G2 , the costmicro-level a method extracts features at the node- orof the matching is 0, and so the similarity is 1. If the1egonet-level; at the mezzo-level it extracts featuresfeature vectors from G1 and G2 are very di erent, thefrom communities; and at the macro-level it extractsmatching is more costly and the similarity is low.features from the global/network level. For the secondTable 1 categorizes our network-similarity methodscriterion, we have 3 types: vector-based, classifier-based,based on the aforementioned two criteria. We brieflyand matching-based. We describe these types below.describe each of these 20 methods below. BecauseVector-based methods assign feature vectors F1macro-level methods consider the entire network atand F2 to each network G1 and G2 , respectively.once, rather than local sub-structures, it is not possibleThey define the similarity between G1 and G2 as 1for such methods to be classifier- or matching-based.2Canberra(F1 , F2 ) [13].More details about these methods is available at http:Classifier-based methods first identify a fixed num//eliassi.org/graphcompareTR.pdf.ber of structures within each network (such as randomVector-based NetSimile [6] first calculates 7 localwalks, communities, or node neighborhoods). For eachstructural features for each node (backed by various social theories). It then calculates the median and the first1 Egonet is the 1-hop induced subgraph around the node.four moments of distribution for each feature. These 5P UV n2 Canberra(U, V ) iii 1 Ui Vi , where n is the number ofstatistics over the 7 features produce a length-35 “signadimensions in U and V . [13]
Random Walk Distances,InfoMap-In, InfoMap-Known, InfoMap-In&KnownAB, BFS, RW, RWRAB-Match, BFS-Match, RW-Match, RWR-MatchMacro-levelDegree, Density, Transitivity,Eigenvalues, LBD––Table 1: The twenty network-similarity methods considered in this paper categorized by (a) the level of networkat which the method operates and (b) the type of comparison used.ture” vector for the network. Classification-based NetSimileSVM samples 300 nodes from each network andcalculates the 7 NetSimile local structural features forthem. Matching-based NetSimile-Match uses the feature vectors obtained by NetSimileSVM. Vector-basedRandom Walk Distances (d-RW-Dist for short) performs 100 random walks of length d (for d 10, 20, 50,and 100) on each network. Each of these walks beginson a randomly selected node u and ends on some othernode v. It then calculates the shortest-path distancebetween u and v in the network. For each value of d,it aggregates these distances over all 100 random walksby calculating the median and first four moments ofdistribution for this set of values. Over all four valuesof d, it produces a length-20 feature vector. Vectorbased InfoMap-In (IMIn), InfoMap-Known (IMKnown), InfoMap-In&Known (IMIn&Known)apply the Infomap community detection algorithm tothe network [18]. For each node n, they identify whichcommunity C that node u is in. IMIn creates a length1 feature vector containing the fraction of each node’sneighbors that are in the same community as the node,averaged over all nodes. IMKnown creates a length1 feature vector containing the fraction of nodes inC that are adjacent to u, averaged over all nodes.IMIn&Known creates a length-2 feature vector containing both of these values. Classification-based AB,BFS, RW, RWR identify 300 communities on eachnetwork via the - swap algorithm [7], breadth-firstsearch, random walk without restart, and random walkwith 15% chance of restart, respectively. For each ofthese communities, they calculate a length-36 featurevector including statistics such as conductance, diameter, density, etc. The full feature vector is describedin [4]. Matching-based AB-Match, BFS-Match,RW-Match, RWR-Match use the same communities and feature vectors as identified by methods AB,BFS, RW, and RWR. Vector-based Density, Degree,Transitivity create a length-1 feature vector containing the density, average degree, or transitivity of eachnetwork. Vector-based Eigenvalues (Eigs) calculatesthe k largest eigenvalues for each network. As in [6],we used k 10. This defines a length-k feature vec-tor. Vector-based LBD computes 3 features from eachnetwork [17]. Leadership measures how much the connectivity of the network is dominated by one vertex.Bonding is simply the transitivity of the network. Diversity calculates the number of disjoint dipoles. Eachnetwork is represented by its length-3 vector.4Comparing Network Similarity MethodsWe are interested in analyzing the relationships betweendi erent network-similarity methods. In particular,we (1) determine the correlations between di erentmethods, (2) locate clusters of methods that behavesimilarly, and (3) identify methods that produce resultsthat summarize the collection of results.Figure 1 contains an overview of our process. Inparticular, we approach this problem from the application of network-similarity ranking. In this application,we are given some reference network Gr and a collection of comparison networks H1 , H2 , · · · , Hk . Using anetwork-similarity method, we calculate the similaritybetween Gr and each Hi , and then rank the comparison networks in order of their similarity to the referencenetwork Gr . By considering the problem from the perspective of ranking rather than considering raw similarity scores, we are able to compare similarity methodsthat may generate similarity scores across very di erentranges. Given a reference network, a collection of comparison networks, and m network similarity methods,we produce m rankings of the comparison networks. Wethen compare the m rankings to one another in orderto determine similarity between the various methods.To determine ranking correlations, we find theKendall-Tau distance between each pair of rankings.Given the rankings from a pair of methods m1 andm2 , the Kendall-Tau distance between the rankings isthe probability that two randomly selected items fromthe rankings are in di erent relative orders in the tworankings. A distance of 0 indicates perfect correlation, adistance of 0.5 indicates no correlation, and a distance of1 indicates an inverse correlation. To confirm the resultsobtained by Kendall-Tau, we also calculate correlationsusing nDCG [9], which gives greater weight to elements
OutputRanking1Kendall 2 SimilarityMethod yMethod 1utOriginalnetwork,GrOutputSimilarityMethod mRankingmKemenyConsensusRankingFigure 1: Flowchart of our two approaches. Both approaches use rankings generated by di erent similaritymethods. In one (top) approach, we use the rankings to correlate and then cluster the network similarity methods.In the second (bottom) approach, we use the rankings to identify a single consensus ail# ofNodes5001220270K740K500K500K37K# Transitivity0.430.240.210.230.040.080.09# ofCC214K36K111KFrac. Nodesin LCC0.9961.00.9150.8511.01.00.918Table 2: Statistics for Our Cross-Sectional Networks. Observe the large variations in statistics across the di erentdatasets. CC stands for connected components. LCC stands for largest connected component.appearing near the beginning of the list. For each pairof methods, we calculate nDCG twice, using each ofthe rankings alternately as the ‘true’ ranking, and thenaverage the results.To find methods that have comparable behavior,we cluster the methods based on the pairwise KendallTau distances. For this step, we use complete-linkagehierarchical clustering because it tends to produce adendrogram with many small clusters, which in turnprovides insight into which groups of methods arevery closely correlated. For each reference network,we perform the complete-linkage hierarchical clusteringl times. In our experiments, we used l 1000.We then select the most common (i.e., representative)dendrogram by (1) considering each dendrogram as atree without information about clustering order and (2)picking the tree that occurs most frequently out of thesel runs as the representative dendrogram. The results ofthis clustering indicate which groups of methods havecomparable behavior. In particular, we are interested inlearning whether any complex methods are associatedwith much simpler methods.To obtain the consensus ranking, we use theKemeny-Young method to combine the set of rankingsinto a single consensus ranking [10]. In this method, mrankings of k items are used to create a k-by-k preference matrix P , where Pij is the number of rankings thatrank item i above item j. Next, each possible rankingR is assigned a score by summing all elements Pij forwhich R ranks i over j. The highest-scoring ranking isconsidered the consensus. Under the assumption thateach ranking is a noisy estimate of a ‘true’ ranking, theKemeny-Young consensus is the maximum likelihood estimator of this true ranking. If some similarity methodconsistently produces rankings that are very close to R,then one can use this method as a representative (i.e.,consensus) of the set of methods.5ExperimentsThis section describes our datasets, methodology, andexperiments on cross-sectional and longitudinal data.
NetworkNameTwitterRepliesTwitterRetweetsYahoo!IM# ofNodes10K–27K# K35K–180K2.5–3.666–123EdgeDensity4.7 10 5 –13 10 52.3 10 5 –8.5 10 53.6 10 5 –8.5 10 5NetworkTransitivity0.0–0.001# ofCC4K–9KFrac. Nodesin �0.20600–3K0.48–0.85Table 3: Statistics for Our Longitudinal Networks. Each dataset contains multiple networks, and so a range ofvalues are presented for each statistic. Observe the large variations in statistics across di erent datasets.5.1 Datasets We use a variety of network datasetsspanning multiple domains. Our experiments are performed on cross-sectional data representing the state ofa network at one moment in time; and on longitudinaldatasets, each containing multiple copies of a networkthat changes over time. Tables 2 and 3 present statisticsfor all of our datasets.Our cross-sectional datasets are as follows. Gradand Undergrad: portions of the Facebook networkcorresponding to graduate and undergraduate studentsat Rice University [15]. DBLP: a computer science coauthorship network [1]. LJ1 and LJ2: portions of theLiveJournal blogging network [5]. Enron: the Enron email network [11]. Amazon: a portion of the productco-purchasing network from Amazon.com [14].Our longitudinal datasets are as follows. TwitterReplies: a collection of 30 networks representing replieson Twitter, aggregated daily over the period of 30 daysin June 2009 [2]. Twitter Retweets: a collection of 5networks representing retweets on Twitter, aggregatedmonthly from May through September of 2009 [2]. Yahoo! IM: a collection of 28 networks representing conversations on the Yahoo! Instant Messaging platform,aggregated daily during April 2008 [3]. These three longitudinal datasets each exhibit very di erent structuralcharacteristics. The Twitter Replies networks are typically very sparse and unstructured: on average, eachconnected component in these networks contains only3 elements, and only 2% of the nodes appear in thelargest connected component. In contrast, the TwitterRetweets and Yahoo! IM networks have more structure,with, respectively, an average connected component sizeof 12 and 22, and a largest connected component containing an average of 73% and 59% of the nodes.5.2 Methodology At the heart of our approach is aset of 20 network-similarity methods described in Section 3. Each of these meth
A Guide to Selecting a Network Similarity Method Sucheta Soundarajan Rutgers University s.soundarajan@cs.rutgers.edu Tina Eliassi-Rad Rutgers University eliassi@cs.rutgers.edu Brian Gallagher Lawrence Livermore Laboratory bgallagher@llnl.gov Abstract We consider the problem of determining how similar two networks (without known node .
work/products (Beading, Candles, Carving, Food Products, Soap, Weaving, etc.) ⃝I understand that if my work contains Indigenous visual representation that it is a reflection of the Indigenous culture of my native region. ⃝To the best of my knowledge, my work/products fall within Craft Council standards and expectations with respect to
akuntansi musyarakah (sak no 106) Ayat tentang Musyarakah (Q.S. 39; 29) لًََّز ãَ åِاَ óِ îَخظَْ ó Þَْ ë Þٍجُزَِ ß ا äًَّ àَط لًَّجُرَ íَ åَ îظُِ Ûاَش
Collectively make tawbah to Allāh S so that you may acquire falāḥ [of this world and the Hereafter]. (24:31) The one who repents also becomes the beloved of Allāh S, Âَْ Èِﺑاﻮَّﺘﻟاَّﺐُّ ßُِ çﻪَّٰﻠﻟانَّاِ Verily, Allāh S loves those who are most repenting. (2:22
Guide to Searching Courses & Selecting a Yonsei Major (Updated Version: July 20, 2017) Selecting a Yonsei major is important in that the information will be used for course registration. Students can choose a major based on the courses they wish to take at Yonsei University. The major at
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software . A. Knopf, Inc. and Penguin Books. . Selecting text 120 Selecting text - quick reference 120 Selecting characters and words 120
A Guide to Selecting and Recruiting District Scouters Selecting district volunteers can be a rewarding experience and is an important task for district and council leaders. It is a personal achievement. Most recruiting involves a “rifle-shot approach”—focusing on individuals— recruiting one person at a time. There are certain principles
A Regional Guide for Farmers, Land Managers, and Gardeners In the Pacific Lowland Mixed Forest Province and NAPPC. 2 Selecting Plants for Pollinators . as butterfly or bird watching. Yet beetles do play a role in pollination. Some have a bad reputation because they can leave a mess States. Selecting Plants for Pollinators Plant
203 FACULTY CODE OF CONDUCT 14 204 RECRUITING & SELECTING NEW FACULTY 15 204.1 Recruiting and Selecting Full-Time Faculty 15 204.2 Recruiting and Selecting Part-Time Faculty 17 205 FACULTY RECORDS 17 206 EVALUATION, TENURE, PROMOTION AND MERIT – NORTH CAMPUS FACULTY 17 206.1 F
