NDLI: Mining Dual Networks: Models, Algorithms, and Applications

Please wait, while we are loading the content...

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 11

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 10

Issue 4(Special Issue on SIGKDD 2014, Special Issue on BIGCHAT and Regular Papers), July 2016

Introduction to the Special Issue of Best Papers in ACM SIGKDD 2014

Product Selection Problem: Improve Market Share by Learning Consumer Behavior

Catching Synchronized Behaviors in Large Networks: A Graph Mining Approach

Heterogeneous Translated Hashing: A Scalable Solution Towards Multi-Modal Similarity Search

Guest Editorial: Special Issue on Connected Health at Big Data Era (BigChat): A TKDD Special Issue

Kernelized Information-Theoretic Metric Learning for Cancer Diagnosis Using High-Dimensional Molecular Profiling Data

Jointly Modeling Label and Feature Heterogeneity in Medical Informatics

Mining Dual Networks: Models, Algorithms, and Applications

Biomedical Ontology Quality Assurance Using a Big Data Approach

Less is More: Building Selective Anomaly Ensembles

Co-Clustering Structural Temporal Data with Applications to Semiconductor Manufacturing

Inferring Dynamic Diffusion Networks in Online Media

Unsupervised Rare Pattern Mining: A Survey

CGC: A Flexible and Robust Approach to Integrating Co-Regularized Multi-Domain Graph for Clustering

Spatial-Proximity Optimization for Rapid Task Group Deployment

Featuring, Detecting, and Visualizing Human Sentiment in Chinese Micro-Blog

Eigen-Optimization on Large Graphs by Edge Manipulation

Issue 3, February 2016

Issue 2, October 2015

Issue 1, July 2015

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 9

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 8

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 7

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 6

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 5

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 4

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 3

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 2

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 1

Mining Dual Networks: Models, Algorithms, and Applications

Content Provider	ACM Digital Library
Author	Li, Li Zhu, Xiaofeng Fan, Wei Wu, Yubao Jin, Ruoming Zhang, Xiang
Copyright Year	2016
Abstract	Finding the densest subgraph in a single graph is a fundamental problem that has been extensively studied. In many emerging applications, there exist $\textit{dual}$ networks. For example, in genetics, it is important to use protein interactions to interpret genetic interactions. In this application, one network represents $\textit{physical}$ interactions among nodes, for example, protein--protein interactions, and another network represents $\textit{conceptual}$ interactions, for example, genetic interactions. Edges in the conceptual network are usually derived based on certain correlation measure or statistical test measuring the strength of the interaction. Two nodes with strong conceptual interaction may not have direct physical interaction. In this article, we propose the novel dual-network model and investigate the problem of finding the densest connected subgraph (DCS), which has the largest density in the conceptual network and is also connected in the physical network. Density in the conceptual network represents the average strength of the measured interacting signals among the set of nodes. Connectivity in the physical network shows how they interact physically. Such pattern cannot be identified using the existing algorithms for a single network. We show that even though finding the densest subgraph in a single network is polynomial time solvable, the DCS problem is NP-hard. We develop a two-step approach to solve the DCS problem. In the first step, we effectively prune the dual networks, while guarantee that the optimal solution is contained in the remaining networks. For the second step, we develop two efficient greedy methods based on different search strategies to find the DCS. Different variations of the DCS problem are also studied. We perform extensive experiments on a variety of real and synthetic dual networks to evaluate the effectiveness and efficiency of the developed methods.
Starting Page	1
Ending Page	37
Page Count	37
File Format	PDF
ISSN	15564681
e-ISSN	1556472X
DOI	10.1145/2785970
Volume Number	10
Issue Number	4
Journal	ACM Transactions on Knowledge Discovery from Data (TKDD)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-05-24
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dual networks Densest connected subgraphs (DCSs)
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks.

Top-k Connected Overlapping Densest Subgraphs in Dual Networks

Finding Densest $k$-Connected Subgraphs

Top-k overlapping densest subgraphs

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n

Towards Realistic Team Formation in Social Networks based on Densest Subgraphs

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

Top-k overlapping densest subgraphs

Top-k Overlapping Densest Subgraphs: Approximation and Complexity

Mining Dual Networks: Models, Algorithms, and Applications

Similar Documents

A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual networks.

Top-k Connected Overlapping Densest Subgraphs in Dual Networks

Finding Densest $k$-Connected Subgraphs

Top-k overlapping densest subgraphs

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n

Towards Realistic Team Formation in Social Networks based on Densest Subgraphs

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

Top-k overlapping densest subgraphs

Top-k Overlapping Densest Subgraphs: Approximation and Complexity

Mining Dual Networks: Models, Algorithms, and Applications