Appendix A: Missing Proofs A.1 Proof of Lemma 1 Proof

For clarity, we decompose Lemma 2 into three lemmas (Lemmas 4-6) and prove each of them. For clarity, we decompose Lemma 3 into three lemmas (Lemmas 7-9) and prove each of them. The proof of Lemma 10 is similar to that of Lemma 1. From the above process, it can be easily seen that Condition 1-3 in the lemma are satisfied. Theorem 3 can also be used to prove Theorem 2, simply by setting p = 1 . By similar reasoning with the proof of Theorem 1 (Appendix A.3), we get It can be easily verified that the social network monitoring problem considered in Section 5 is a non-monotone submodular maximization problem subject to a partition matroid constraint.