Problem

My problem is to profile the individual user (i.e. mine individual user's interest, location, and many more).

What we have as input are the network structure (e.g. linked-in network) including user set $V$ and link set $E$ and the attributes for each user (e.g. affiliations, employment, skills). There is NO explicit weight on the link, of course. The attributes are only available for a subset of labeled user $V_l$.

A user $u_i \in V$ has have partial attributes or no attribute available. Now we want to infer those attributes from his friends. The intuition is that if all friends of $u_i$ are PhD students in University B, then $u_i$ is very likely to be a student in University B.

To solve this problem, the first step is to select a proper set of user $V_r$ to propagate their attributes to $u_i$. The criteria of $V_r$ is

1. They are relevant to $u_i$.
2. At least one of them has available attributes.

Existing Solution for $V_r$ selection

In social networks analysis, I only know the following two kinds of networks:

1. Whole social networks -- all the nodes and links among them.
2. Ego network -- a focal node and all the directly connected nodes (1-hop neighbors) and all the links among those nodes.

In my opinion, using the whole social network is not feasible. From social network service, we can collect millions of users, most of whom may be completely irrelevant to our target. Besides, the full network structure is unavailable to public in general. Therefore, I want a proper sub-network. However, the ego network seems to be too small. Because, some nodes may have only a few directly connected neighbors.

I want to know what other $V_r$ can I use and why.

Extra Problem

It is clear that the ego network is one connected component. Is the whole social network necessary one connected component?

If not, then there should be several connected components in this "whole" social network. Then given one focal node, we can find one connected component centered on this node. Is there a terminology (such as ego network) on this kind of network?

• "I want to know what choice people usually make, and why." Choice as far as what? I think a considerable amount of detail is missing from this problem description. Concerning sampling, if you state an actual scientific question, there's no need to sample the whole network, just a subset of nodes to produce conditional independence among relevant nodes. However, you can make no statistical inference by only sampling a focal node, you also must sample other similar individuals and their nodes for conditional independence to make inference on variations in path structure/weight. – AdamO Mar 17 '14 at 16:38
• Thank you @AdamO for your comments. I add more detailed description there. I do not understand the "conditional independence" subset. Can you elaborate more? How to select the subset is my problem. Sorry, if I did not make it clear at the beginning. – thekingofkings Mar 17 '14 at 17:35
• @thekingofkings You have missed the entire class of sampled networks, such as those formed by snowball or respondent driven sampling schemes. – Fomite Mar 17 '14 at 18:31
• @thekingofkings social networks can be represented as DAGs (Direct Acyclic Graphs). You can contrast that with other types of graphical models, such as those where no edge is directed, or those where you have combinations of single or double headed arrows. It's important to have directions when estimating social networks because it allows you to concisely describe specific relationships. Conditional independence in graphical models is an important concept to understand. I think this slide set is a very good start. – AdamO Mar 17 '14 at 18:46
• Really appreciate your keywords and supplemental materials. Very helpful for me. – thekingofkings Mar 17 '14 at 20:09