Search

Centrality measures for simple graphs are well-defined and several main-memory algorithms exist for each. Simple graphs are not adequate for modeling complex data sets with multiple entities and relationships. Multilayer networks (MLNs) have been shown to be better suited, but there are very few algorithms for centrality computation directly on MLNs. They are converted (aggregated or collapsed) to simple graphs using Boolean AND or OR operators to compute centrality, which is not only inefficient but incurs a loss of structure and semantics. In this paper, we propose algorithms that compute closeness centrality on an MLN directly using a novel decoupling-based approach. Individual results of layers (or simple graphs) of an MLN are used and a composition function developed to compute the centrality for the MLN. The challenge is to do this accurately and efficiently. However, since these algorithms do not have complete information of the MLN, computing a global measure such as closeness centrality is a challenge. Hence, these algorithms rely on heuristics derived from intuition. The advantage is that this approach lends itself to parallelism and is more efficient compared to the traditional approach. We present two heuristics for composition and experimentally validate accuracy and efficiency on a large number of synthetic and real-world graphs with diverse characteristics.

Centrality measures for simple graphs/networks are well-defined and each has numerous main-memory algorithms. However, for modeling complex data sets with multiple types of entities and relationships, simple graphs are not ideal. Multilayer networks (or MLNs) have been proposed for modeling them and have been shown to be better suited in many ways. Since there are no algorithms for computing centrality measures directly on MLNs, existing strategies reduce (aggregate or collapse) the MLN layers to simple networks using Boolean AND or OR operators. This approach negates the benefits of MLN modeling as these computations tend to be expensive and furthermore results in loss of structure and semantics. In this paper, we propose heuristic-based algorithms for computing centrality measures (specifically, degree centrality) on MLNs directly (i.e., without reducing them to simple graphs) using a newly-proposed decoupling-based approach which is efficient as well as structure and semantics preserving. We propose multiple heuristics to calculate the degree centrality using the network decoupling-based approach and compare accuracy and precision with Boolean OR aggregated Homogeneous MLNs (HoMLN) for ground truth. The network decoupling approach can take advantage of parallelism and is more efficient compared to aggregation-based approaches. Extensive experimental analysis is performed on large synthetic and real-world data sets of varying characteristics to validate the accuracy and efficiency of our proposed algorithms.

Any data analysis, especially the data sets that may be changing often or in real-time, consists of at least three important synchronized components: i) figuring out what to infer (objectives), ii) analysis or computation of objectives, and iii) understanding of the results which may require drill-down and/or visualization. There is a lot of attention paid to the first two of the above components as part of research whereas the understanding as well as deriving actionable decisions is quite tricky. Visualization is an important step towards both understanding (even by non-experts) and inferring the actions that need to be taken. As an example, for Covid-19, knowing regions (say, at the county or state level) that have seen a spike or prone to a spike in cases in the near future may warrant additional actions with respect to gatherings, business opening hours, etc. This paper focuses on an extensible architecture for visualization of base as well as analyzed data. This paper proposes a modular architecture of a dashboard for user-interaction, visualization management, and complex analysis of base data. The contributions of this paper are: i) extensibility of the architecture providing flexibility to add additional analysis, visualizations, and user interactions without changing the workflow, ii) decoupling of the functional modules to ease and speedup development by different groups, and iii) address efficiency issues for display response time. This paper uses Multilayer Networks (or MLNs) for analysis. To showcase the above, we present the implementation of a visualization dashboard, termed CoWiz++ (for Covid Wizard), and elaborate on how web-based user interaction and display components are interfaced seamlessly with the back end modules.

Any large complex data analysis to infer or discover meaningful information/knowledge involves the following steps (in addition to data collection, cleaning, preparing the data for analysis such as attribute elimination): i) Modeling the data -- an approach for modeling and deriving a data representation for analysis using that approach, ii) translating analysis objectives into computations on the model generated; this can be as simple as a single computation (e.g., community detection) or may involve a sequence of operations (e.g., pair-wise community detection over multiple networks) using expressions based on the model, iii) computation of the expressions generated -- efficiency and scalability come into picture here, and iv) drill-down of results to interpret or understand them clearly. Beyond this, it is also meaningful to visualize results for easier understanding. Covid-19 visualization dashboard presented in this paper is an example of this. This paper covers all of the above steps of data analysis life cycle using a data representation that is gaining importance for multi-entity, multi-feature data sets - Multilayer Networks. We use several data sets to establish the effectiveness of modeling using MLNs and analyze them using the proposed decoupling approach. For coverage, we use different types of MLNs for modeling, and community and centrality computations for analysis. The data sets used - US commercial airlines, IMDb, DBLP, and Covid-19 data set. Our experimental analyses using the identified steps validate modeling, breadth of objectives that can be computed, and overall versatility of the life cycle approach. Correctness of results is verified, where possible, using independently available ground truth. We demonstrate drill-down that is afforded by this approach (due to structure and semantics preservation) for a better understanding and visualization of results.

As the use of MultiLayer Networks (or MLNs) for modeling and analysis is gaining popularity, it is becoming increasingly important to propose a community definition that encompasses the multiple features represented by MLNs and develop algorithms for efficiently computing communities on MLNs. Currently, communities for MLNs, are based on aggregating the networks into single graphs using different techniques (type independent, projection-based, etc.) and applying single graph community detection algorithms, such as Louvain and Infomap on these graphs. This process results in different types of information loss (semantics and structure). To the best of our knowledge, in this paper we propose, for the first time, a definition of community for heterogeneous MLNs (or HeMLNs) which preserves semantics as well as the structure. Additionally, our basic definition can be extended to appropriately match the analysis objectives as needed. In this paper, we present a structure and semantics preserving community definition for HeMLNs that is compatible with and is an extension of the traditional definition for single graphs. We also present a framework for its efficient computation using a newly proposed decoupling approach. First, we define a k-community for connected k layers of a HeMLN. Then we propose a family of algorithms for its computation using the concept of bipartite graph pairings. Further, for a broader analysis, we introduce several pairing algorithms and weight metrics for composing binary HeMLN communities using participating community characteristics. Essentially, this results in an extensible family of community computations. We provide extensive experimental results for showcasing the efficiency and analysis flexibility of the proposed computation using popular IMDb and DBLP data sets., Comment: arXiv admin note: substantial text overlap with arXiv:1910.01737, arXiv:1903.02641

Datasets of real-world applications are characterized by entities of different types, which are defined by multiple features and connected via varied types of relationships. A critical challenge for these datasets is developing models and computations to support flexible analysis, i.e., the ability to compute varied types of analysis objectives in an efficient manner. To address this problem, in this paper, we make a case for modeling such complex data sets as multilayer networks (or MLNs), and argue that MLNs provide a more informative model than the currently popular simple and attribute graphs. Through analyzing communities and hubs on homogeneous and heterogeneous MLNs, we demonstrate the flexibility of the chosen model. We also show that compared to current analysis approaches, a network decoupling-based analysis of MLNs is more efficient and also preserves the structure and result semantics. We use three diverse data sets to showcase the effectiveness of modeling them as MLNs and analyzing them using the decoupling-based approach. We use both homogeneous and heterogeneous MLNs for modeling and community and hub computations for analysis. The data sets are from US commercial airlines and IMDb, a large international movie data set. Our experimental analysis validate modeling, efficiency of computation, and versatility of the approach. Correctness of results are verified using independently available ground truth. For the data sets used, efficiency improvement is in the range of 64% to 98%.

Multilayer networks or MLNs (also called multiplexes or network of networks) are being used extensively for modeling and analysis of data sets with multiple entity and feature types and associated relationships. Although the concept of community is widely-used for aggregate analysis, a structure- and semantics preserving definition for it is lacking for MLNs. Retention of original MLN structure and entity relationships is important for detailed drill-down analysis. In addition, efficient computation is also critical for large number of analysis. In this paper, we introduce a structure-preserving community definition for MLNs as well as a framework for its efficient computation using the decoupling approach. The proposed decoupling approach combines communities from individual layers to form a serial k-community for connected k layers in a MLN. We propose a new algorithm for pairing communities across layers and introduce several weight metrics for composing communities from two layers using participating community characteristics. In addition to the definition, our proposed approach has a number of desired characteristics. It: i) leverages extant single graph community detection algorithms, ii) introduces several weight metrics that are customized for the community concept, iii) is a new algorithm for pairing communities using bipartite graphs, and iv) experimentally validates the community computation and its efficiency on widely-used IMDb and DBLP data sets., Comment: arXiv admin note: substantial text overlap with arXiv:1903.02641

Networks (or graphs) are used to model the dyadic relations between entities in a complex system. In cases where there exists multiple relations between the entities, the complex system can be represented as a multilayer network, where the network in each layer represents one particular relation (or feature). The analysis of multilayer networks involves combining edges from specific layers and then computing a network property. Different subsets of the layers can be combined. For any Boolean combination operation (e.g. AND, OR), the number of possible subsets is exponential to the number of layers. Thus recomputing for each subset from scratch is an expensive process. In this paper, we propose to efficiently analyze multilayer networks using a method that we term network decomposition. Network decomposition is based on analyzing each network layer individually and then aggregating the analysis results. We demonstrate the effectiveness of using network decomposition for detecting communities on different combinations of network layers. Our results on multilayer networks obtained from real-world and synthetic datasets show that our proposed network decomposition method requires significantly lower computation time while producing results of high accuracy.

Multi-feature data analysis (e.g., on Facebook, LinkedIn) is challenging especially if one wants to do it efficiently and retain the flexibility by choosing features of interest for analysis. Features (e.g., age, gender, relationship, political view etc.) can be explicitly given from datasets, but also can be derived from content (e.g., political view based on Facebook posts). Analysis from multiple perspectives is needed to understand the datasets (or subsets of it) and to infer meaningful knowledge. For example, the influence of age, location, and marital status on political views may need to be inferred separately (or in combination). In this paper, we adapt multilayer network (MLN) analysis, a nontraditional approach, to model the Facebook datasets, integrate content analysis, and conduct analysis, which is driven by a list of desired application based queries. Our experimental analysis shows the flexibility and efficiency of the proposed approach when modeling and analyzing datasets with multiple features., Comment: 18 pages

With the advent of social networks and the web, the graph sizes have grown too large to fit in main memory precipitating the need for alternative approaches for an efficient, scalable evaluation of queries on graphs of any size. Here, we use the divide and conquer approach by partitioning a graph and process queries over partitions to obtain all or specified number of answers. This entails correctly computing answers that span multiple partitions or even need the same partition more than once. Given a set of partitions, there are many approaches to evaluate a query: i) One Partition At a Time approach, ii) Traditional use of Multiple Processors, and iii) using the Map/Reduce Multi-Processor approach. Approach (i), detailed in this paper, has established scalability through independent processing of partitions. The other two approaches address response time in addition to scalability. For approach (i), necessary minimal book keeping has been identified and its correctness established in this paper. Query answering on partitioned graphs also requires analyzing partitioning schemes for their impact on query processing and determining the number and the sequence in which partitions need to be loaded to reduce the response time to process queries. We correlate query properties and partition characteristics to reduce query processing time in terms of the resources available. We also identify a set of quantitative metrics and use them to formulate heuristics to determine the order of loading partitions for efficient query processing. For approach (i), experiments on large graphs (synthetic, real-world) using different partitioning schemes analyze the proposed heuristics on a variety of query types. The other two approaches are fleshed out and analyzed. An existing graph querying system has been extended to evaluate queries on partitioned graphs. Finally all approaches are contrasted.

Multilayer networks or MLNs (also called multiplexes or network of networks) are being used extensively for modeling and analysis of data sets with multiple entity and feature types as well as their relationships. As the concept of communities and hubs are used for these analysis, a structure-preserving definition for them on MLNs (that retains the original MLN structure and node/edge labels and types) and its efficient detection are critical. There is no structure-preserving definition of a community for a MLN as most of the current analyses aggregate a MLN to a single graph. Although there is consensus on community definition for single graphs (and detection packages) and to a lesser extent for homogeneous MLNs, it is lacking for heterogeneous MLNs. In this paper, we not only provide a structure-preserving definition for the first time, but also its efficient computation using a decoupling approach, and discuss its characteristics & significance for analysis. The proposed decoupling approach for efficiency combines communities from individual layers to form a serial k-community for connected k layers in a MLN. We propose several weight metrics for composing layer-wise communities using the bipartite graph match approach based on the analysis semantics. Our proposed approach has a number of advantages. It: i) leverages extant single graph community detection algorithms, ii) is based on the widely-used maximal flow bipartite graph matching for composing k layers, iii) introduces several weight metrics that are customized for the community concept, and iv) experimentally validates the definition, mapping, and efficiency from a flexible analysis perspective on widely-used IMDb data set. Keywords: Heterogeneous Multilayer Networks; Bipartite Graphs; Community Definition and Detection; Decoupling-Based Composition, Comment: 27 pages, Submitted to VLDB 2019

Holistic analysis of many real-world problems are based on data collected from multiple sources contributing to some aspect of that problem. The word fusion has also been used in the literature for such problems involving disparate data types. Holistically understanding traffic patterns, causes of accidents, bombings, terrorist planning and many natural phenomenon such as storms, earthquakes fall into this category. Some may have real-time requirements and some may need to be analyzed after the fact (post-mortem or forensic analysis.) What is common for all these problems is that the amount and types of data associated with the event. Data may also be incomplete and trustworthiness of sources may also vary. Currently, manual and ad-hoc approaches are used in aggregating data in different ways for analyzing and understanding these problems. In this paper, we approach this problem in a novel way using multilayered networks. We identify features of a central event and propose a network layer for each feature. This approach allows us to study the effect of each feature independently and its impact on the event. We also establish that the proposed approach allows us to compose these features in arbitrary ways (without loss of information) to analyze their combined effect. Additionally, formulation of relationships (e.g., distance measure for a single feature instead of several at the same time) is simpler. Further, computations can be done once on each layer in this approach and reused for mixing and matching the features for aggregate impacts and "what if" scenarios to understand the problem holistically. This has been demonstrated by recreating the communities for the AND-Composed network by using the communities of the individual layers. We believe that techniques proposed here make an important contribution to the nascent yet fast growing area of data fusion.