2015 ReciprocityinSocialNetworkswith

• (Jiang et al., 2015) ⇒ Bo Jiang, Zhi-Li Zhang, and Don Towsley. (2015). “Reciprocity in Social Networks with Capacity Constraints.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783410

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Reciprocity+in+Social+Networks+with+Capacity+Constraints
• http://dl.acm.org/citation.cfm?id=2783258.2783410&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; degree sequence; directed graph; network problems; reciprocity; social network

Abstract

Directed links -- representing asymmetric social ties or interactions (e.g.," follower-followee ") -- arise naturally in many social networks and other complex networks, giving rise to directed graphs (or digraphs) as basic topological models for these networks. Reciprocity, defined for a digraph as the percentage of edges with a reciprocal edge, is a key metric that has been used in the literature to compare different directed networks and provide “hints" about their structural properties: for example, are reciprocal edges generated randomly by chance or are there other processes driving their generation? In this paper we study the problem of maximizing achievable reciprocity for an ensemble of digraphs with the same prescribed in- and out-degree sequences. We show that the maximum reciprocity hinges crucially on the in- and out-degree sequences, which may be intuitively interpreted as constraints on some “social capacities” of nodes and impose fundamental limits on achievable reciprocity. We show that it is NP-complete to decide the achievability of a simple upper bound on maximum reciprocity, and provide conditions for achieving it. We demonstrate that many real networks exhibit reciprocities surprisingly close to the upper bound, which implies that users in these social networks are in a sense more “social” than suggested by the empirical reciprocity alone in that they are more willing to reciprocate, subject to their “social capacity” constraints. We find some surprising linear relationships between empirical reciprocity and the bound. We also show that a particular type of small network motifs that we call 3-paths are the major source of loss in reciprocity for real networks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 ReciprocityinSocialNetworkswith	Zhi-Li Zhang Bo Jiang Don Towsley			Reciprocity in Social Networks with Capacity Constraints				10.1145/2783258.2783410		2015