## Abstract

A key operation in network analysis is the discovery of cohesive subgraphs. The notion of κ-truss has gained considerable popularity in this regard, based on its rich structure and efficient computability. However, many complex networks such as social, biological and communication networks feature uncertainty, best modeled using probabilities. Unfortunately the problem of discovering κ-trusses in probabilistic graphs has received little attention to date. In this paper, given a probabilistic graph G, number κ and parameter γ ∈ (0, 1], we define a (κ, γ)-truss as a maximal connected subgraph H ⊆ G, in which for each edge, the probability that it is contained in at least (κ - 2) triangles is at least γ. We develop an efficient dynamic programming algorithm for decomposing a probabilistic graph into such maximal (κ, γ)-trusses. The above definition is local in that the "witness" graphs that has the (κ - 2) triangles containing an edge in H may be quite different for distinct edges. Hence, we also propose global (κ, γ)-truss, which in addition to being a local (κ, γ)-truss, has to satisfy the condition that the probability that H contains a κ-truss is at least γ. We show that unlike local (κ, γ)-trusses, the global (κ, γ)-truss decomposition on a probabilistic graph is intractable. We propose a novel sampling technique which enables approximate discovery of global (κ, γ)-trusses with high probability. Our extensive experiments on real datasets demonstrate the efficacy of our proposed approach and the usefulness of local and global (κ, γ)-truss.

Original language | English |
---|---|

Title of host publication | SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data |

Publisher | Association for Computing Machinery (ACM) |

Pages | 77-90 |

Number of pages | 14 |

ISBN (Print) | 9781450335317 |

DOIs | |

Publication status | Published - 26 Jun 2016 |

Event | ACM SIGMOD International Conference on Management of Data, SIGMOD 2016 - San Francisco, United States Duration: 26 Jun 2016 → 1 Jul 2016 https://dl.acm.org/doi/proceedings/10.1145/2882903 |

### Publication series

Name | Proceedings of the ACM SIGMOD International Conference on Management of Data |
---|---|

Volume | 26-June-2016 |

ISSN (Print) | 0730-8078 |

### Conference

Conference | ACM SIGMOD International Conference on Management of Data, SIGMOD 2016 |
---|---|

Country/Territory | United States |

City | San Francisco |

Period | 26/06/16 → 1/07/16 |

Internet address |

## Scopus Subject Areas

- Software
- Information Systems