Monotonicity in Undirected Networks
Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This question can be formally stated as a property of the centrality measure that defines the importance of the actors of the network. Score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relatively to the remaining nodes. It is known that most centralities are both score and rank monotone on directed, strongly connected graphs. In this paper, we study the problem of score and rank monotonicity for classical centrality measures in the case of undirected networks: in this case, we require that score, or relative importance, improve at both endpoints of the new edge. We show that, surprisingly, the situation in the undirected case is very different, and in particular that closeness, harmonic centrality, betweenness, eigenvector centrality, Seeley's index, Katz's index, and PageRank are not rank monotone; betweenness and PageRank are not even score monotone. In other words, while it is always a good thing to get a new follower, it is not always beneficial to get a new friend.
Code (1)
Tasks
ARCSimilar Papers 제목 키워드 기반
Spectral Rank Monotonicity on Undirected Networks
We study the problem of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in the case of undirected networks. Score monotonicity means that adding an edge increases th…
PositionHow to address monotonicity for model risk management?
In this paper, we study the problem of establishing the accountability and fairness of transparent machine learning models through monotonicity. Although there have been numerous studies on individual monotonicity, pairw…
Additive modelsFairnessManagementWeak comonotonicity
The classical notion of comonotonicity has played a pivotal role when solving diverse problems in economics, finance, and insurance. In various practical problems, however, this notion of extreme positive dependence stru…
Can neural networks understand monotonicity reasoning?
Monotonicity reasoning is one of the important reasoning skills for any intelligent natural language inference (NLI) model in that it requires the ability to capture the interaction between lexical and syntactic structur…
Data AugmentationNatural Language InferenceFailure of monotonicity in epidemic models
We discuss the failure of monotonicity properties for even simple compartmental epidemic models, for the case where transmission rates are non-constant. We also identify a special case in which monotonicity holds.