Fair Information Spread on Social Networks with Community Structure
Octavio Mesner Elizaveta Levina Ji Zhu
Information spread through social networks is ubiquitous. Influence maximiza-
tion (IM) algorithms aim to identify individuals who will generate the greatest
spread through the social network if provided with information, and have been
largely devel- oped with marketing in mind. In social networks with community
structure, which are very common, IM algorithms focused solely on maximizing
spread may yield signifi- cant disparities in information coverage between
communities, which is problematic in settings such as public health messaging.
While some IM algorithms aim to remedy disparity in information coverage using
node attributes, none use the empirical com- munity structure within the
network itself, which may be beneficial since communities directly affect the
spread of information. Further, the use of empirical network struc- ture allows
us to leverage community detection techniques, making it possible to run
fair-aware algorithms when there are no relevant node attributes available, or
when node attributes do not accurately capture network community structure. In
contrast to other fair IM algorithms, this work relies on fitting a model to
the social network which is then used to determine a seed allocation strategy
for optimal fair information spread. We develop an algorithm to determine
optimal seed allocations for expected fair coverage, defined through maximum
entropy, provide some theoretical guarantees under appropriate conditions, and
demonstrate its empirical accuracy on both simu- lated and real networks.
Because this algorithm relies on a fitted network model and not on the network
directly, it is well-suited for partially observed and noisy social networks.