  Network inference is the process of deciding what is the true unknown graph
underlying a set of interactions between nodes. There is a vast literature on
the subject, but most known methods have an important drawback: the inferred
graph is not guaranteed to explain every interaction from the input trace. We
consider this an important issue since such inferred graph cannot be used as
input for applications that require a reliable estimate of the true graph. On
the other hand, a graph having trace feasibility guarantees can help us better
understand the true (hidden) interactions that may have taken place between
nodes of interest. The inference of such graph is the goal of this paper.
Firstly, given an activity log from a social network, we introduce a set of
constraints that take into consideration all the hidden paths that are possible
between the nodes of the trace, given their timestamps of interaction. Then, we
develop a nontrivial modification of the Expectation-Maximization algorithm by
Newman [1], that we call Constrained-EM, which incorporates the constraints and
a set of auxiliary variables into the inference process to guide it towards the
feasibility of the trace. Experimental results on real-world data from Twitter
confirm that Constrained-EM generates a posterior distribution of graphs that
explains all the events observed in the trace while presenting the desired
properties of a scale-free, small-world graph. Our method also outperforms
established methods in terms of feasibility and quality of the inferred graph.
