| Title | : | Algorithms for Rich Graph structures |
| Speaker | : | Tarun Kumar (IITM) |
| Details | : | Fri, 20 Dec, 2019 2:00 PM @ AM Turing Hall |
| Abstract: | : | Many real-world systems can be characterized by several components that interact in multiple ways. Such systems are observed in various domains such as brain networks in biology, railway networks in transportation systems, multiple computers connected on the internet, humans involved in multifaceted relationships, etc. These systems can be modeled by various complex graph structures such as hypergraphs, multilayer networks, knowledge graphs, multipartite graphs, etc. Extending traditional graph algorithms to these complex graph structures has numerous bottlenecks and demand non-trivial solutions. In this work, we focus on two such complex graph structures viz. hypergraphs and multilayer networks. For hypergraphs, we propose a computationally efficient community detection algorithm that works on the principles of modularity maximization. We also propose a neighbourhood similarity-based algorithm to predict novel hyperedges for a given hypergraph. In multilayer networks, we propose a set of centrality measures. A central open question in extending centrality measures to multilayer networks is the assessment of the local effect of a node in its layer vs. the global effects of the node in the overall network or specific target layers or target node sets. In this study, we propose several PageRank-like iterative centrality measures that offer these local vs. global effects of nodes by decomposing the overall multilayer centrality into relative contributions from intra-layer vs. inter-layer edges. We show that these measures have desirable theoretical properties like decomposability and derive the necessary conditions for convergence. For validation, we run our proposed centrality measure on multiple synthetic datasets and show how our proposed measures capture the local and global importance of nodes very efficiently, where existing approaches fail. |
