Along　the　development　of　social　networks,　predicting　the　quality　of　connections　between　two　individuals　has　been　attracting　research　interest　from　both　industrial　and　research　community.　For　many　social　applications　with　the　prediction　requirement,　the　personalities　(labels)　of　individuals　within　the　relationship　(connections)　were　known　to　have　a　significant　impact　against　the　analysis,　observing　two　neighbored　individuals　acquiring　an　identical　label　are　more　likely　to　affect　each　other　than　those　are　only　with　different　labels.　In　the　paper,　we　tackle　with　a　more　practical　problem　in　which　an　individual　has　several　labels,　rather　than　considering　only　an　identical　label　for　all　individuals.　For　the　task,　we　first　present　multi-label　independent　cascade　(MIC)　model　which　is　in　fact　a　generalization　of　the　classical　IC　model,　and　then　in　a　multi-label　social　network,　we　propose　two　algorithms　for　analyzing　the　maximum　connectivity　between　two　individuals.　The　first　is　a　heuristic　algorithm,　which,　generalizing　the　maximal　flow　algorithm,　is　based　on　repeatedly　finding　shortest　augmenting　path;　the　second　is　based　on　linear-programming　(LP)　and　produces　optimum　solutions.　At　last,　we　evaluate　the　two　algorithms　by　experiments　through　their　practical　performance　and　runtime.　©　2019　IEEE.