Discovering fortress-like cohesive subgraphs

Li, C; Zhang, F; Zhang, Y; Qin, L; Zhang, W; Lin, X

Discovering fortress-like cohesive subgraphs

Li, C

Zhang, F Zhang, Y

Qin, L

Zhang, W Lin, X

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Journal Article
Citation:: Knowledge and Information Systems, 2021, 63, (12), pp. 3217-3250
Issue Date:: 2021-12-01

Closed Access

	Filename	Description	Size
	Li2021_Article_DiscoveringFortress-likeCohesi.pdf	Published version	1.64 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Li, C https://orcid.org/0000-0002-6164-2643
dc.contributor.author	Zhang, F
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.date.accessioned	2022-01-29T01:08:20Z
dc.date.available	2022-01-29T01:08:20Z
dc.date.issued	2021-12-01
dc.identifier.citation	Knowledge and Information Systems, 2021, 63, (12), pp. 3217-3250
dc.identifier.issn	0219-1377
dc.identifier.issn	0219-3116
dc.identifier.uri	http://hdl.handle.net/10453/153779
dc.description.abstract	Morris (Rev Econ Stud 67:57–78, 2000) defines the p-cohesion by a connected subgraph in which every vertex has at least a fraction p of its neighbors in the subgraph, i.e., at most a fraction (1 - p) of its neighbors outside. We can find that a p-cohesion ensures not only inner-cohesiveness but also outer-sparseness. The textbook on networks by Easley and Kleinberg (Networks, Crowds, and Markets - Reasoning About a Highly Connected World, Cambridge University Press, 2010) shows that p-cohesions are fortress-like cohesive subgraphs which can hamper the entry of the cascade, following the contagion model. Despite the elegant definition and promising properties, to our best knowledge, there is no existing study on p-cohesion regarding problem complexity and efficient computing algorithms. In this paper, we fill this gap by conducting a comprehensive theoretical analysis on the complexity of the problem and developing efficient computing algorithms. We focus on the minimal p-cohesion because they are elementary units of p-cohesions and the combination of multiple minimal p-cohesions is a larger p-cohesion. We demonstrate that the discovered minimal p-cohesions can be utilized to solve the MinSeed problem: finding a smallest set of initial adopters (seeds) such that all the network users are eventually influenced. Extensive experiments on 8 real-life social networks verify the effectiveness of this model and the efficiency of our algorithms.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation	http://purl.org/au-research/grants/arc/DP160101513
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation.ispartof	Knowledge and Information Systems
dc.relation.isbasedon	10.1007/s10115-021-01624-x
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0801 Artificial Intelligence and Image Processing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	Discovering fortress-like cohesive subgraphs
dc.type	Journal Article
utslib.citation.volume	63
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2022-01-29T01:08:18Z
pubs.issue	12
pubs.publication-status	Published
pubs.volume	63
utslib.citation.issue	12

Abstract:

Morris (Rev Econ Stud 67:57–78, 2000) defines the p-cohesion by a connected subgraph in which every vertex has at least a fraction p of its neighbors in the subgraph, i.e., at most a fraction (1 - p) of its neighbors outside. We can find that a p-cohesion ensures not only inner-cohesiveness but also outer-sparseness. The textbook on networks by Easley and Kleinberg (Networks, Crowds, and Markets - Reasoning About a Highly Connected World, Cambridge University Press, 2010) shows that p-cohesions are fortress-like cohesive subgraphs which can hamper the entry of the cascade, following the contagion model. Despite the elegant definition and promising properties, to our best knowledge, there is no existing study on p-cohesion regarding problem complexity and efficient computing algorithms. In this paper, we fill this gap by conducting a comprehensive theoretical analysis on the complexity of the problem and developing efficient computing algorithms. We focus on the minimal p-cohesion because they are elementary units of p-cohesions and the combination of multiple minimal p-cohesions is a larger p-cohesion. We demonstrate that the discovered minimal p-cohesions can be utilized to solve the MinSeed problem: finding a smallest set of initial adopters (seeds) such that all the network users are eventually influenced. Extensive experiments on 8 real-life social networks verify the effectiveness of this model and the efficiency of our algorithms.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/153779