Landline and mobile phone companies and broadband providers will be ordered to store the data for a year and make it available to the security services under the scheme.
The databases would not record the contents of calls, texts or emails but the numbers or email addresses of who they are sent and received by.
For the first time, the security services will have widespread access to information about who has been communicating with each other on social networking sites such as Facebook.
Direct messages between subscribers to websites such as Twitter would also be stored, as well as communications between players in online video games.
The Home Office is understood to have begun negotiations with internet companies in the last two months over the plan, which could be officially announced as early as May.